SPOJ-LCS sam

LCS.cpp

#include <cstdio>
#include <cstring>
#include <algorithm>
const int N = 250000 * 2 + 9;
char s[N];
struct SAM
{
    int l[N],ch[N][26],fa[N],cnt,len,last;
    void init(){cnt = last = 1; len = 0;memset(ch[1],0,sizeof ch[1]);}
    void add(int c)
    {
        int np = ++cnt,p = last; last = np;
        l[np] = ++len; memset(ch[np],0,sizeof ch[np]);
        for (; p && !ch[p][c]; p = fa[p]) ch[p][c] = np;
        if (!p) fa[np] = 1;
        else {
            int q = ch[p][c];
            if (l[q] == l[p] + 1) fa[np] = q;
            else {
                int nq = ++cnt;
                fa[nq] = fa[q];
                l[nq] = l[p] + 1;
                memcpy(ch[nq],ch[q],sizeof ch[q]);
                fa[q] = fa[np] = nq;
                for (; ch[p][c] == q; p = fa[p]) ch[p][c] = nq;
            }
        }
    }
    int work(char *s)
    {
        int res = 0;
        for (int p = 1,len = 0; *s; ++s) {
            int c = *s - 'a';
            while (p && !ch[p][c]) p = fa[p];
            if (!p) p = 1,len = 0;
            else {
                len = std::min(l[p],len) + 1;
                p = ch[p][c];
            }
            //printf("%d\n",len);
            res = std::max(res,len);
        }
        return res;
    }
}sam;
int main()
{
    #ifndef ONLINE_JUDGE
    freopen("LCS.in","r",stdin);
    freopen("LCS.out","w",stdout);
    #endif
    scanf("%s",s);
    sam.init();
    for (char *c = s; *c; ++c) sam.add(*c - 'a');
    scanf("%s",s);
    printf("%d\n",sam.work(s));
}