最近发现我字符串很菜（你这话不对，你不是上个学期就已经是整个机房字符串最菜的吗）。我好像经常忘板子（其实写这篇的时候我已经忘了SA怎么写了）。所以写篇博客吧，若以后再忘可以帮助记忆。

SAM和PAM这两个自动机长得比较像，可以一起记。

这里目前只有基础的版本，只能处理单串问题。广义的版本以后某时再补上（发出咕咕的声音）。

SAM 后缀自动机

如何背板：
记住一个循环：for (; p && !go[p][c]; p = par[p]) go[p][c] = np;
记住一个条件：len[q] == len[p] + 1
记得设根为1，不能用空结点做根

伪代码

设0为空结点，1为根
extend(c) {新建 np 并设置 len （其实是设置除par外的所有属性，因为go为空）for (!go[p][c]) go[p][c] = np;if (!p) par = 1;else {par[p] 本应是 q = go[p][c]，但必须 len[q] = len[p] + 1if (len[q] == len[p] + 1) par[p] = q;else {新建 nq: 除 len = len[p] + 1 外都与q一样for (go[p][c] == q) go[p][c] = nq;par[np] = par[q] = nq;}}p = np;
}

代码

int go[N][26], par[N], len[N], cnt = 1, p = 1;
void extend(int c) {int np = ++cnt;len[np] = len[p] + 1;for (; p && !go[p][c]; p = par[p]) go[p][c] = np;if (!p) par[np] = 1;else {int q = go[p][c];if (len[q] == len[p] + 1) par[np] = q;else {int nq = ++cnt;len[nq] = len[p] + 1;par[nq] = par[q];memcpy(go[nq], go[q], sizeof *go);for (; p && go[p][c] == q; p = par[p]) go[p][c] = nq;par[np] = par[q] = nq;  //be aware}}p = np;
}

PAM 回文自动机

如何背板：
记住一个循环：while (s[i-len[p]-1] ^ s[i]) p = fail[p];
记得0根为0号，-1根为1号。这样可以使其余结点的fail自动指向0根

当go[p][c]为空时新建结点，注意一定要把go[p][c] = np留到最后来设置。
否则会导致第一个加入的结点fail指向自己。现象是在插入第二个字符时死循环。
如果模板写挂了，调试最好先输出每次新建结点的fail和len，用aaaa和abacaba可以排除大部分错。

int go[N][26], fail[N], len[N], np = 1, p = 0;
void init() {len[1] = -1; fail[0] = fail[1] = 1;}
void extend(int i, int c) {while (s[i-len[p]-1] ^ s[i]) p = fail[p];int &ch = go[p][c];if (!ch) {len[++np] = len[p] + 2;do p = fail[p];while (s[i-len[p]-1] ^ s[i]);fail[np] = go[p][c];ch = np;    //be aware}p = ch;
}