SPOJ 1811 Longest Common Substring拡張子自動機

テンプレートソース：http://www.neroysq.com/?p=76
考え方：http://blog.sina.com.cn/s/blog_7812 e 9860012 dfv.
つまり、2つの文字列の最長の共通部分の列を求めて、最大25000文字列を連結します。
Aを直列にして拡張子のモチーフを構築し、Bを通してマッチングします。エニュメレート列Bの各ビットB[i]は、B[i]を終端とするすべてのサブストリングを考慮し、維持された値はB[i]を終端としてマッチングできる最大長tmpLとする。
B[i]に行くとストリングスにマッチしていますが、現在のノードにB[i]という息子がいたら、まっすぐ下に行ってください。
もしないなら、failポインタに沿って前に戻ります。息子がいるノードが見つかるまで。

#include <cstdio>

#include <cstring>

#include <cstdlib>

#include <algorithm>



using namespace std;



const int MAXN = 250010;

const int SigmaSize = 26;



struct sanode

{

    sanode *f, *ch[SigmaSize];

    int l;

};



struct Suffix_Automaton

{

    sanode pool[ ( MAXN << 1 ) + 20 ];

    sanode *init;

    sanode *tail;

    int tot;



    void Clear()

    {

        tot = 0;

        init = pool;

        tail = init;

        return;

    }



    void Insert( int c )

    {

        sanode *q = pool + ( ++tot ), *p = tail;

        q->l = p->l + 1;

        for ( ; p && !p->ch[c]; p = p->f ) p->ch[c] = q;

        tail = q;

        if ( !p ) q->f = init;

        else

        {

            if ( p->ch[c]->l == p->l + 1 ) q->f = p->ch[c];

            else

            {

                sanode *r = pool + ( ++tot ), *u = p->ch[c];

                *r = *u;

                r->l = p->l + 1;

                u->f = q->f = r;

                for ( ; p && p->ch[c] == u; p = p->f ) p->ch[c] = r;

            }

        }

    }

};



char str[MAXN + 20];

Suffix_Automaton SAM;



int main()

{

    int len;

    scanf( "%s", str + 1 );



    SAM.Clear();

    len = strlen( str + 1 );

    for ( int i = 1; i <= len; ++i )

        SAM.Insert( str[i] - 'a' );

    sanode *p = SAM.init;

    scanf( "%s", str + 1 );

    len = strlen( str + 1 );

    int tmpL = 0, ans = 0;

    for ( int i = 1; i <= len; ++i )

    {

        if ( p->ch[ str[i] - 'a' ] )   //                

            p = p->ch[ str[i] - 'a' ], ++tmpL;

        else  //    p  str[i]    

        {

            while ( p && !p->ch[ str[i] - 'a' ] ) 
　　　　　　　　　 p = p->f; //  fail     ，     str[i]     ，      

            if( p )  //        str[i]     

            {

                tmpL = p->l + 1;

                p = p->ch[ str[i] - 'a' ];

            }

            else     //          

            {

                p = SAM.init;

                tmpL = 0;

            }

        }

        ans = max( ans, tmpL );

    }



    printf( "%d
", ans );

    return 0;

}