后缀自动机.doc

后缀自动机
目录
POJ-1509 Glass Beads ............................................................................................................... 1
SPOJ-1811 mon Substring .................................................................................... 2
SPOJ-8222 Substrings ................................................................................................................ 3
SPOJ-1812 mon Substring II ................................................................................. 4
SPOJ-7258 Lexicographical Substring Search ............................................................................ 6
HDU-4622 Reincarnation .......................................................................................................... 7
HDU-4641 K-string .................................................................................................................... 9
POJ-1509 Glass Beads
题意:求一个字符串的最小表示的开始下标。
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 10005;
char str[N];
struct SAM {
struct Node {
int ch[26];
int f, len;
void init() {
f = -1, len = 0;
memset(ch, 0xff, sizeof (ch));
}
};
Node sn[N<<1];
int idx, last;
void init() {
idx = last = 0;
sn[idx++].init();
}
int newnode() {
sn[idx].init();
return idx++;
}
void add(int c) {
int end = newnode();
int tmp = last;
sn[end].len = sn[last].len + 1;
for ( ; tmp != -1 && sn[tmp].ch[c] == -1; tmp = sn[tmp].f) {
sn[tmp].ch[c] = end;
}
if (tmp == -1) sn[end].f = 0; // 所有的上一轮可接受点都没有指向字符c的孩子节点
else {
int nxt = sn[tmp].ch[c];
if (sn[tmp].len + 1 == sn[nxt].len) sn[end].f = nxt; // 如果可接受点有向c的转移,且长度只加1,那么该孩子可以替代当前的end,并且end的双亲指向该孩子
else {
int np = newnode();
sn[np] = sn[nxt];
sn[np].len = sn[tmp].len + 1;
sn[end].f = sn[nxt].f = np;
for (; tmp != -1 && sn[tmp].ch[c] == nxt; tmp = sn[tmp].f) { sn[tm