SA 后缀数组 / SAM 后缀自动机 c++ 模板

前言

SA 后缀数组模板
SAM 后缀自动机模板

代码

1.SA

#include <cstring>
#include <iostream>
using namespace std;
const int maxn = 1e6 + 6;
char s[maxn];
int rk[maxn], sa[maxn], height[maxn];
int sa2[maxn], oldrk[maxn], tank[maxn];
int n, m;
bool cmp(int x, int y, int w) {
  return oldrk[x] == oldrk[y] && oldrk[x + w] == oldrk[y + w];
}
void rsort() {  // sa2为基数排序而构造
  for (int i = 1; i <= m; i++) tank[i] = 0;
  for (int i = 1; i <= n; i++) tank[rk[sa2[i]]]++;
  for (int i = 2; i <= m; i++) tank[i] += tank[i - 1];
  for (int i = n; i >= 1; i--) sa[tank[rk[sa2[i]]]--] = sa2[i];
}
void getSA() {
  for (int i = 1; i <= n; i++) rk[i] = s[i], sa2[i] = i;
  rsort();  // 对SA进行基数排序
  for (int k = 1; k <= n; k <<= 1) {
    int cnt = 0;  // 对第二关键字的SA2进行排序(非计数排序)
    for (int i = n - k + 1; i <= n; i++) sa2[++cnt] = i;
    for (int i = 1; i <= n; i++)
      if (sa[i] > k) sa2[++cnt] = sa[i] - k;
    rsort();  // 对SA进行基数排序(与rk本质同,只是排序的方式不同)
    swap(rk, oldrk);
    cnt = 1;  // 对rk进行倍增比较排序
    rk[sa[1]] = 1;
    for (int i = 2; i <= n; i++) {
      if (cmp(sa[i], sa[i - 1], k))
        rk[sa[i]] = cnt;
      else
        rk[sa[i]] = ++cnt;
    }
    m = cnt;
  }
}
void getHI() {
  int k = 0;
  for (int i = 1; i <= n; i++) {
    if (rk[i] == 1) continue;
    int j = sa[rk[i] - 1];
    if (k) k--;
    while (i + k <= n && j + k <= n && s[i + k] == s[j + k]) k++;
    height[rk[i]] = k;
  }
}
int main() {
  // freopen("in.txt", "r", stdin);
  // freopen("out.txt", "w", stdout);
  scanf("%s", s + 1);
  n = strlen(s + 1);
  m = 127;
  getSA();
  getHI();
  printf("rk: ");
  for (int i = 1; i <= n; i++) printf("%d ", rk[i]);
  printf("\n");
  printf("sa: ");
  for (int i = 1; i <= n; i++) printf("%d ", sa[i]);
  printf("\n");
  return 0;
}

2.SAM

#include <cstring>
#include <iostream>
#include <map>
using namespace std;
const int maxn = 100000;
char s[maxn];
struct state {
  int len, link;
  map<char, int> next;
};
state st[maxn * 2];
int cnt, last;
void samInit() {
  st[0].len = 0;
  st[0].link = -1;
  cnt = 1;
  last = 0;
}
void samExtend(char c) {
  int cur = cnt++;
  st[cur].len = st[last].len + 1;
  int p = last;
  while (p != -1 && !st[p].next.count(c)) {
    st[p].next[c] = cur;
    p = st[p].link;
  }
  if (p == -1) {
    st[cur].link = 0;
  } else {
    int q = st[p].next[c];
    if (st[p].len + 1 == st[q].len) {
      st[cur].link = q;
    } else {
      int clone = cnt++;
      st[clone].len = st[p].len + 1;
      st[clone].next = st[q].next;
      st[clone].link = st[q].link;
      while (p != -1 && st[p].next[c] == q) {
        st[p].next[c] = clone;
        p = st[p].link;
      }
      st[q].link = st[cur].link = clone;
    }
  }
  last = cur;
}
int main() {
  //   freopen("in.txt", "r", stdin);
  //   freopen("out.txt", "w", stdout);
  scanf("%s", s);
  int len = strlen(s);
  samInit();
  for (int i = 0; i < len; i++) {
    samExtend(s[i]);
  }
  return 0;
}