string.rst

String

KMP

int fail[N], len;
void buildF(char *p) {
  for (int i = 1, j = fail[0] = -1; i < len; ++i) {
    while (~j && p[i] != p[j + 1]) j = fail[j];
    fail[i] = j += p[i] == p[j + 1];
  }
}
int kmp(char *s, char *p) {
  len = strlen(p); buildF(p);
  int ret (0);
  for (int i = 0, j = -1; s[i]; ++i) {
    while (~j && s[i] != p[j + 1]) j = fail[j];
    if (s[i] == p[j + 1]) ++j;
    if (j == len - 1) {
      ++ret;
      j = fail[j];
    }
  }
  return ret;
}
// all repetends
vector<int> r; //empty
void get_r() {
  int now = len - 1;
  while (~now) {
    r.push_back(len - 1 - fail[now]);
    now = fail[now];
  }
}

extKMP

// str = "aaaba", pat = "aba", then ex[] = {1, 1, 3, 0, 1}, ext[] = {3, 0, 1}
int const N = 200200;
int ext[N], ex[N];
void extkmp(char *str, char *pat, int ext[], int ex[]) {
  int la = strlen(str), lb = strlen(pat);
  int p = 0, k = 1;
  while (pat[p] == pat[p + 1]) ++p;
  ext[0] = lb, ext[1] = p;
  for (int i = 2; i < lb; ++i) {
    int x = k + ext[k] - i, y = ext[i - k];
    if (y < x) ext[i] = y;
    else {
      p = max(0, x);
      while (pat[p] == pat[p + i]) ++p;
      ext[i] = p;
      k = i;
    }
  }
  p = k = 0;
  while (str[p] && str[p] == pat[p]) ++p;
  ex[0] = p;
  for (int i = 1; i < la; ++i) {
    int x = k + ex[k] - i, y = ext[i - k];
    if (y < x) ex[i] = y;
    else {
      p = max(0, x);
      while (pat[p] && pat[p] == str[p + i]) ++p;
      ex[i] = p;
      k = i;
    }
  }
}

Trie

int const N = 100100; // size
int const M = 32;     // length
struct Trie {
  int idx, cnt;
  struct Trie_Node {
    int id;
    Trie_Node *next[26];
    void init() {
      id = -1;
      clr(next, NULL);
    }
  } trie[N*M], root;

  int insert(char* s) {
    Trie_Node *p = &root;
    for (int i = 0; s[i]; ++i) {
      int j = s[i] - 'a';
      if (p -> next[j] == NULL) {
        trie[idx].init();
        p -> next[j] = &trie[idx++];
      }
      p = p -> next[j];
    }
    if (p -> id == -1) p -> id = cnt++;
    return p -> id;
  }
  void init() {
    root.init();
    idx = cnt = 0;
  }
};

MinimumRepresentation

int mins(char *s, int n) {
  int i = 0, j = 1, len = 0, x, y;
  while (i < n && j < n && len < n) {
    x = i + len; if (x >= n) x -= n;
    y = j + len; if (y >= n) y -= n;
    if (s[x] == s[y]) ++len;
    else if (s[x] < s[y]) j += len + 1, len = 0;
    else i = j++, len = 0;
  }
  return i;
}

Manacher

struct Manacher {
  int p[N<<1], len; char str[N<<1];
  int id, ret; // maxPalindrome_idx, maxPalindrome_length
  void func() {
    int mx (0);
    id = 0;
    rep(i, len) {
      if (mx > i) p[i] = min(p[id + id - i], mx - i);
      else p[i] = 1;
      for (; str[i + p[i]] == str[i - p[i]]; ++p[i]);
      ret = max(ret, p[i]);
      if (p[i] + i > mx) {
        mx = p[i] + i;
        id = i;
      }
    }
    --ret;
  }
  void init(char *s) {
    // "aaa" -> "!#a#a#a#"
    len = 0; str[len++]= '!', str[len++] = '#';
    for (int i = 0; s[i]; ++i) {
      str[len++] = s[i];
      str[len++] = '#';
    }
    str[len] = 0;
    ret = 0;
    func();
  }
  bool check(int l, int r) {
    if ((r - l) % 2 == 0) {
      int mid = (r + l) / 2;
      mid = mid * 2 + 2;
      return p[mid] == r - l + 2;
    } else {
      int mid = (l + 1 + r + 1);
      return p[mid] == r - l + 2;
    }
  }
};

SuffixArray

int const N = 200200;
int arr[3][N], cnt[N], mc[256], h[N], *sa, *ta, *r, *tr, sz;
void sa_init(char *str, int len) {
  sa = arr[0], ta = arr[1], r = arr[2], sz = 0;
  rep(i, len) ta[i] = str[i];
  sort(ta, ta + len);
  Rep(i, len) {
    if (ta[i] != ta[i - 1] || i == len) {
      cnt[mc[ta[i - 1]] = sz++] = i;
    }
  }
  for (int i = len - 1; i >= 0; --i) {
    sa[--cnt[r[i] = mc[str[i]]]] = i;
  }
  for (int k = 1; k < len && r[sa[len - 1]] < len - 1; k <<= 1) {
    for (int i = 0; i < len; i++) {
      cnt[r[sa[i]]] = i + 1;
    }
    for (int i = len - 1; i >= 0; --i) {
      if (sa[i] >= k) {
        ta[--cnt[r[sa[i] - k]]] = sa[i] - k;
      }
    }
    for (int i = len - k; i < len; ++i) {
      ta[--cnt[r[i]]] = i;
    }
    tr = sa, sa = ta, tr[sa[0]] = 0;
    for (int i = 1; i < len; ++i) {
      tr[sa[i]] =
        tr[sa[i - 1]] + (r[sa[i]] != r[sa[i - 1]] || sa[i - 1] + k >= len || r[sa[i] + k] != r[sa[i - 1] + k]);
    }
    ta = r, r = tr;
  }

  for (int i = 0, d = 0, j; i < len; ++i) {
    if (str[i] == '#' || r[i] == len - 1) {
      h[r[i]] = d = 0;
    } else {
      if (d) {
        --d;
      }
      j = sa[r[i] + 1];
      while (str[i + d] != '#' && str[j + d] != '#' && str[i + d] == str[j + d]) {
        ++d;
      }
      h[r[i]] = d;
    }
  }
}

Aho-corasick(trie graph)

int root, idx;
struct trie_node{
    int next[size];
    int fail;
    bool flag;
    void init(){
        fail = -1, flag = false;
        memset(next, 0, sizeof(next));
    }
}trie[maxn * leng];
int q[maxn * leng];
void trie_init(){
    root = idx = 0;
    trie[root].init();
}
void insert(char *s){
    int i, j, p = root;
    for(i=0;s[i];i++){
        j = s[i] - 'A';
        if(!trie[p].next[j]){
            trie[++idx].init();
            trie[p].next[j] = idx;
        }
        p = trie[p].next[j];
    }
    trie[p].flag = true;
}
void build(){
    int j, p;
    q[0] = root;
    for(int l=0,h=1;l<h;){
        p = q[l++];
        for(j=0;j<size;j++){
            if(trie[p].next[j]){
                q[h++] = trie[p].next[j];
                if(trie[p].fail == -1)
                    trie[trie[p].next[j]].fail = root;
                else{
                    trie[trie[p].next[j]].fail =
                        trie[trie[p].fail].next[j];

                    trie[trie[p].next[j]].flag |=
                        trie[trie[trie[p].fail].next[j]].flag;
                }
            }
            else{
                if(trie[p].fail != -1)
                    trie[p].next[j] = trie[trie[p].fail].next[j];
            }
        }
    }
}