spoj1812 LCS2 - Longest Common Substring II

地址：http://www.spoj.com/problems/LCS2/

题面：

LCS2 - Longest Common Substring II

no tags

A string is finite sequence of characters over a non-empty finite set Σ.

In this problem, Σ is the set of lowercase letters.

Substring, also called factor, is a consecutive sequence of characters occurrences at least once in a string.

Now your task is a bit harder, for some given strings, find the length of the longest common substring of them.

Here common substring means a substring of two or more strings.

Input

The input contains at most 10 lines, each line consists of no more than 100000 lowercase letters, representing a string.

Output

The length of the longest common substring. If such string doesn't exist, print "0" instead.

Example

Input:

alsdfkjfjkdsal

fdjskalajfkdsla

aaaajfaaaa

Output:

2

Notice: new testcases added

思路：

对第一个穿构建sam，然后让后面的串在sam上走，同时记录每个串跑完后各个状态的所能匹配的最长长度，然后对所有串取个最小值，之后再取个最大值。

注意：如果状态p能够到达，那么状态fa[p]也必然能够到达，但可能在匹配时不会走到fa[p]状态，所以当p可达时，要更新fa[p]。

 #include <bits/stdc++.h>

 using namespace std;

 struct SAM

 {

     static const int MAXN = <<;//大小为字符串长度两倍

     static const int LetterSize = ;

     int tot, last, ch[MAXN][LetterSize], fa[MAXN], len[MAXN];

     int sum[MAXN], tp[MAXN]; //用于拓扑排序，tp为排序后的数组

     void init( void)

     {

         last = tot = ;

         len[] = ;

         memset(ch,,sizeof ch);

         memset(fa,,sizeof fa);

     }

     void add( int x)

     {

         int p = last, np = last = ++tot;

         len[np] = len[p] + ;

         while( p && !ch[p][x]) ch[p][x] = np, p = fa[p];

         if( p == )

             fa[np] = ;

         else

         {

             int q = ch[p][x];

             if( len[q] == len[p] + )

                 fa[np] = q;

             else

             {

                 int nq = ++tot;

                 memcpy( ch[nq], ch[q], sizeof ch[q]);

                 len[nq] = len[p] + , fa[nq] = fa[q], fa[q] = fa[np] = nq;

                 while( p && ch[p][x] == q)  ch[p][x] = nq, p = fa[p];

             }

         }

     }

     void toposort( void)

     {

         for(int i = ; i <= len[last]; i++)   sum[i] = ;

         for(int i = ; i <= tot; i++)   sum[len[i]]++;

         for(int i = ; i <= len[last]; i++)   sum[i] += sum[i-];

         for(int i = ; i <= tot; i++)   tp[sum[len[i]]--] = i;

     }

 } sam;

 char ss[];

 int ans,mx[<<],mi[<<];

 int main(void)

 {

     //freopen("in.acm","r",stdin);

     sam.init();

     scanf("%s",ss);

     for(int i=,len=strlen(ss);i<len;i++)  sam.add(ss[i]-'a');

     for(int i=;i<=sam.tot;i++) mi[i]=1e6;

     sam.toposort();

     while(~scanf("%s",ss))

     {

         for(int i=,len=strlen(ss),p=,cnt=;i<len;i++)

         {

             int c=ss[i]-'a';

             if(sam.ch[p][c])

                 p=sam.ch[p][c],cnt++;

             else

             {

                 while(p&&!sam.ch[p][c]) p=sam.fa[p];

                 if(!p)

                     p=,cnt=;

                 else

                     cnt=sam.len[p]+,p=sam.ch[p][c];

             }

             mx[p]=max(mx[p],cnt);

         }

         for(int i=sam.tot;i;i--)

         {

             int p=sam.tp[i];

             mi[p]=min(mx[p],mi[p]);

             if(mx[p]&&sam.fa[p]) mx[sam.fa[p]]=sam.len[sam.fa[p]];

             mx[p]=;

         }

     }

     for(int i=;i<=sam.tot;i++) ans=max(ans,mi[i]);

     printf("%d\n",ans);

     return ;

 }