POJ 1509 Glass Beads【后缀自动机、最小表示法】

此题为最简单的后缀自动机的应用。

#include <iostream>#include <cstring>#include <cstdio>#include <algorithm>#include <cmath>using namespace std;const int maxn = 10010;struct SamNode {    int ch[26];    int par, len;    void Init() {        par = -1;        len = 0;        memset(ch, -1, sizeof(ch));    }};class SAM{public:    void Init() {        tot = 0;        last = 0;        sn[0].Init();    }    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].par) {            sn[tmp].ch[c] = end;        }        if (tmp == -1) {            sn[end].par = 0;        } else {            int nxt = sn[tmp].ch[c];            if (sn[tmp].len + 1 == sn[nxt].len) {                sn[end].par = nxt;            } else {                int np = NewNode();                sn[np] = sn[nxt];                sn[np].len = sn[tmp].len + 1;                sn[end].par = sn[nxt].par = np;                for ( ; tmp != -1 && sn[tmp].ch[c] == nxt; tmp = sn[tmp].par) {                    sn[tmp].ch[c] = np;                }            }        }        last = end;    }    int tot;    int last;    SamNode sn[maxn*4];    int NewNode() {        sn[++tot].Init();        return tot;    }};int t, n;char s[maxn];SAM sam;int main(){    scanf("%d", &t);    while (t--) {        scanf("%s", s);        sam.Init();        n = strlen(s);        for (int i = 0; i < n; ++i) {            sam.Add(s[i] - 'a');        }        for (int i = 0; i < n; ++i) {            sam.Add(s[i] - 'a');        }        int now = 0;        for (int i = 0; i < n; ++i) {            for (int j = 0; j < 26; ++j) {                if (sam.sn[now].ch[j] != -1) {                    now = sam.sn[now].ch[j];                    break;                }            }        }        printf("%d\n", sam.sn[now].len - n + 1);    }    return 0;}