kuangbin 的模板

//begin{ kuangbin SAM }struct SAM_Node {  SAM_Node *fa, *next[CHAR];  int len, id, pos;  SAM_Node(int _len = 0): fa(0), len(_len), id(0), pos(0) {memset(next, 0, sizeof(next));}};SAM_Node SAM_node[MAXN * 2], *SAM_root, *SAM_last;int SAM_size;SAM_Node *newSAM_Node(int len) {SAM_node[SAM_size] = SAM_Node(len); SAM_node[SAM_size].id = SAM_size; return &SAM_node[SAM_size++];}SAM_Node *newSAM_Node(SAM_Node *p) {SAM_node[SAM_size] = *p; SAM_node[SAM_size].id = SAM_size; return &SAM_node[SAM_size++];}void SAM_init() {SAM_size = 0; SAM_root = SAM_last = newSAM_Node(0); SAM_node[0].pos = 0;}void SAM_add(int x, int len) {  SAM_Node *p = SAM_last, *np = newSAM_Node(p->len + 1);  np->pos = len; SAM_last = np;  for(; p && !p->next[x]; p = p->fa) p->next[x] = np;  if(!p) { np->fa = SAM_root; return;}  SAM_Node *q = p->next[x];  if(q->len == p->len + 1) { np->fa = q; return;}  SAM_Node *nq = newSAM_Node(q);  nq->len = p->len + 1; q->fa = nq; np->fa = nq;  for(; p && p->next[x] == q; p = p->fa) p->next[x] = nq;}void SAM_build(char *s) {  SAM_init();  int len = strlen(s);  for(int i = 0; i < len; i++) SAM_add(s[i] - 'a', i + 1);}int topocnt[MAXN];SAM_Node *topsam[MAXN * 2];void topo() {  int n = strlen(s);  SAM_build(s);  memset(topocnt, 0, sizeof(topocnt));  for(int i = 0; i < SAM_size; i++)topocnt[SAM_node[i].len]++;  for(int i = 1; i <= n; i++)topocnt[i] += topocnt[i - 1];  for(int i = 0; i < SAM_size; i++)topsam[--topocnt[SAM_node[i].len]] = &SAM_node[i];}// end{kaungbin SAM}

 

求最长公共子串长度

char s1[MAXN], s2[MAXN];void solve() {  gets(s1); gets(s2);  SAM_build(s1);  int ans = 0;  SAM_Node *p = SAM_root;  for(int i = 0, t = 0, len = strlen(s2); i < len; ++i) {    if(p->next[s2[i] - 'a']) {      p = p->next[s2[i] - 'a'];      t++;    } else {      while(p != NULL && !p->next[s2[i] - 'a'])  p = p->fa;      if(p == NULL)  p = SAM_root, t = 0;      else t = p->len + 1, p = p->next[s2[i] - 'a'];    }    ans = std::max(ans, t);  }  printf("%d\n", ans);}

求字典序最小循环移位（可用最小表示法）

char s1[MAXN];void solve() {  gets(s1); SAM_build(s1);  int len = strlen(s1);  for(int i = 0; i < len; ++i)  SAM_add(s1[i] - 'a', len + i + 1);  SAM_Node *p = SAM_root;  for(int i = 0, t = 0, len = strlen(s1); i < len; ++i) {    int j = 0;    while(p->next[j] == NULL && j < 26) j++;    p = p->next[j];  }  int ans = p->pos - len + 1;  printf("%d\n", ans);}

依次输出长度为 i （from 1 to |s|） 的所有子串中出现的最多次数

 

const int MAXN = 500000+7; // r(表示当前状态可以在多少个位置上出现)// mi(当前状态能接受的串的最短长度，即 par->val+1)int r[MAXN],mi[MAXN],ret[MAXN];void solve() {  gets(s); topo();  int len = strlen(s);  SAM_Node *p = SAM_root;  for(int i = 0; i < len; ++i){    p = p->next[s[i]-'a'];    r[p->id] = 1;  }  for(int i = SAM_size - 1; i > 0; --i) {    p = topsam[i];    r[p->fa->id] += r[p->id];    mi[p->id] = mi[p->fa->id];  }  for(int i = 1;i < SAM_size;++i){    p = topsam[i];    ret[p->len] = std::max(ret[p->len],r[p->id]);    //printf("f[%d]=%d\n",p->len,r[p->id]);  }  for(int i = len-1;i>0;--i)  ret[i] = std::max(ret[i+1],ret[i]);  for(int i = 1;i <= len;++i){    printf("%d\n",ret[i]);  }}

上面代码中 MAXN = 250000+7 时返回 WA 

~~~~(>_<)~~~~

字典序第 K 小子串

int v[MAXN * 2], c[MAXN], son[MAXN][26];char ret[MAXN], ch[MAXN][26];void solve() {  gets(s); topo();  int len = strlen(s);  SAM_Node *p = SAM_root;  for(int i = 0; i < SAM_size; i++) v[topsam[i]->id] = 1;  for(int i = SAM_size - 1; i >= 0; --i) {    p = topsam[i];    for(int j = 0; j < 26; ++j) {      if(p->next[j] == NULL) continue;      int x = p - SAM_root, y = p->next[j] - SAM_root;      son[x][c[x]] = y, ch[x][c[x]++] = j + 'a', v[p->id] += v[p->next[j]->id];    }  }  int n; scanf("%d", &n);  while(n--) {    int k, pos = 0, x = 0; scanf("%d", &k);    while(k > 0) {      for(int j = 0; j < c[x]; ++j) {        p = SAM_root + son[x][j];        if(v[p->id] >= k){k --, ret[pos++] = ch[x][j], x = son[x][j]; break;}        else k -= v[p->id];      }    }    ret[pos] = 0; puts(ret);  }}

<2017-08-09 Wed> 添加字典序第 k 小子串