use rand::{RngExt, rng};
use crate::{
strings::{ASCII_SIZE, char_at},
utilities::is_prime,
};
pub struct SubstringSearch;
const R: usize = ASCII_SIZE;
#[must_use = "building the pattern does not evaluate it"]
pub struct KMPPattern {
m: usize,
dfa: Vec<Vec<usize>>,
}
impl KMPPattern {
pub fn new(pattern: String) -> Self {
assert!(!pattern.is_empty(), "Pattern cannot be empty!!!");
let mut dfa = Vec::with_capacity(R);
dfa.resize_with(R, || vec![0; pattern.len()]);
dfa[char_at(&pattern, 0) as usize][0] = 1;
let mut curr = 0;
for j in 1..pattern.len() {
for item in dfa.iter_mut().take(R) {
item[j] = item[curr]; }
dfa[char_at(&pattern, j) as usize][j] = j + 1; curr = dfa[char_at(&pattern, j) as usize][curr]; }
Self {
m: pattern.len(),
dfa,
}
}
}
#[must_use = "building the pattern does not evaluate it"]
pub struct BoyerMoorePattern {
right: Vec<isize>,
pattern: String,
}
impl BoyerMoorePattern {
pub fn new(pattern: String) -> Self {
assert!(!pattern.is_empty(), "Pattern cannot be empty!!!");
let mut right = vec![-1; R];
for j in 0..pattern.len() {
right[char_at(&pattern, j) as usize] = j as isize;
}
Self { pattern, right }
}
}
#[must_use = "building the pattern does not evaluate it"]
pub struct RabinKarp {
pattern: String,
pat_hash: u64,
prime: u32,
remainder: u64,
}
const I31_MAX: u32 = 0x7FFF_FFFF;
fn gen_prime() -> u32 {
loop {
let mut num = rng().random_range(0..=I31_MAX);
num |= 1 << 30; num |= 1;
if is_prime(&num, 16) {
return num;
}
}
}
fn rabin_karp_hash(key: &str, len: usize, prime: u64) -> u64 {
let mut h = 0u64;
for j in 0..len {
h = (R as u64 * h + char_at(key, j) as u64) % prime;
}
h
}
fn rabin_karp_check(txt: &str, pat: &str, i: usize) -> bool {
for j in 0..pat.len() {
if char_at(pat, j) != char_at(txt, i + j) {
return false;
}
}
true
}
impl RabinKarp {
pub fn new(pattern: String) -> Self {
assert!(!pattern.is_empty(), "Pattern cannot be empty!!!");
let pat_len = pattern.len();
let prime = gen_prime();
let mut remainder = 1;
for _ in 1..=(pat_len - 1) {
remainder = (R as u64 * remainder) % (prime as u64);
}
let pat_hash = rabin_karp_hash(&pattern, pat_len, prime as u64);
Self {
pattern,
pat_hash,
prime,
remainder,
}
}
}
impl SubstringSearch {
#[must_use]
pub fn brute_force(pat: &str, txt: &str) -> usize {
let m = pat.len();
let n = txt.len();
for i in 0..=(n - m) {
let mut j = 0;
while j < m {
if char_at(txt, i + j) != char_at(pat, j) {
break;
}
j += 1;
}
if j == m {
return i; }
}
n }
#[must_use]
pub fn kmp(pat: &KMPPattern, txt: &str) -> usize {
let (mut i, mut j, n) = (0, 0, txt.len());
while i < n && j < pat.m {
j = pat.dfa[char_at(txt, i) as usize][j];
i += 1;
}
if j == pat.m { i - pat.m } else { n }
}
#[must_use]
pub fn bm(pat: &BoyerMoorePattern, txt: &str) -> usize {
let (n, m) = (txt.len(), pat.pattern.len());
let mut skip;
let mut i = 0;
while i <= n - m {
skip = 0;
for j in (0..m).rev() {
let c = char_at(txt, i + j);
if char_at(&pat.pattern, j) != c {
skip = (j as isize - pat.right[c as usize]).min(1);
}
}
if skip == 0 {
return i; }
i += skip as usize;
}
n }
#[must_use]
pub fn rk(pat: &RabinKarp, txt: &str) -> usize {
let txt_len = txt.len();
let pat_len = pat.pattern.len();
let prime = pat.prime as u64;
if txt_len < pat_len {
return txt_len;
}
let mut txt_hash = rabin_karp_hash(txt, pat_len, prime);
if pat.pat_hash == txt_hash && rabin_karp_check(txt, &pat.pattern, 0) {
return 0;
}
for i in pat_len..txt_len {
txt_hash = (txt_hash + prime
- pat.remainder * char_at(txt, i - pat_len) as u64 % prime)
% prime;
txt_hash = (txt_hash * R as u64 + char_at(txt, i) as u64) % prime;
let offset = i - pat_len + 1;
if pat.pat_hash == txt_hash
&& rabin_karp_check(txt, &pat.pattern, offset)
{
return offset;
}
}
txt_len
}
}