Shift-And アルゴリズム

string.shift-and.rs

fn shift_and(text: &String, pattern: &String) -> Option<usize> {
    let text_chars = text.chars().map(|c| c as usize).collect::<Vec<_>>();
    let pattern_chars = pattern.chars().map(|c| c as usize).collect::<Vec<_>>();
    let n = text.len();
    let m = pattern.len();
    let g = 1 << (m - 1);

    let mut d = [0; 300];
    for i in 0..m { d[pattern_chars[i]] ^= 1 << i }

    let mut x: usize = 0;
    for i in 0..n {
        x = (1 | (x << 1)) & d[text_chars[i]];
        if x & g > 0 { return Some(i+1-m) }
    }
    return None
}

Example

fn test(s: &str, t: &str) {
    let a = String::from(s);
    let b = String::from(t);
    println!("{:?} {:?} {:?}", s, t, shift_and(&a, &b));
}

fn main() {
    test("ABC", "BCX");    // "ABC" "BCX" None
    test("ABC", "BX");     // "ABC" "BX" None
    test("ABC", "X");      // "ABC" "X" None
    test("ABC", "BC");     // "ABC" "BC" Some(1)
    test("ABC", "B");      // "ABC" "B" Some(1)
    test("ABC", "C");      // "ABC" "C" Some(2)
    test("ABC", "AC");     // "ABC" "AC" None
    test("ABC", "AB");     // "ABC" "AB" Some(0)
    test("ABC", "A");      // "ABC" "A" Some(0)
    test("BACABAB", "AB"); // "BACABAB" "AB" Some(3)
}

string.shift-and.cc

int shift_and(string text, string pattern) {
  using T = unsigned int;
  // using T = unsigned long

  const int n = text.size();
  const int m = pattern.size();
  assert(sizeof(T) * 8 >= m);

  const T M = 1 << (m - 1);
  T d[300] = {0};
  // map<char, T> d;

  rep (i, m) d[pattern[i]] ^= 1 << i;
  T x = 0;
  rep (i, n) {
    x = (1 | (x << 1)) & d[text[i]];
    if (x & M) return i - m + 1;
  }
  return -1;
}

Example

void test(string s, string t) {
  auto r = shift_and(s, t);
  cout << s << ' ' << t << ' ' << r << endl;
}

int main()
{
  test("ABC", "BCX");    // ABC BCX -1
  test("ABC", "BX");     // ABC BX -1
  test("ABC", "X");      // ABC X -1
  test("ABC", "BC");     // ABC BC 1
  test("ABC", "B");      // ABC B 1
  test("ABC", "C");      // ABC C 2
  test("ABC", "AC");     // ABC AC -1
  test("ABC", "AB");     // ABC AB 0
  test("ABC", "A");      // ABC A 0
  test("BACABAB", "AB"); // BACABAB AB 3
}