SPOJ LCS2 多个串的最长公共子串

这里串最多有10个，找所有串的最长公共子串

这里后缀自动机做，以第一个串建立后缀自动机，后面的串一个个去匹配，每次得到当前串在可到达状态上所能得到的最长后缀长度

拿所有串匹配后得到的结果进行计算

 #include <iostream>

 #include <cstdio>

 #include <cstring>

 using namespace std;

 #define M 26

 #define N 200100

 char str[N];

 struct SamNode{

     SamNode *son[M] , *f;

     int l , nc , c;

 }sam[N] , *last , *root , *b[N];

 int cnt , num[N];

 void init()

 {

     root = last = &sam[cnt=];

 }

 void add(int x)

 {

     SamNode *p = &sam[++cnt] , *jp=last;

     p->l = jp->l+ , p->nc = p->l;

     last = p;

     for( ; jp&&!jp->son[x] ; jp=jp->f) jp->son[x]=p;

     if(!jp) p->f = root;

     else{

         if(jp->l+ == jp->son[x]->l) p->f = jp->son[x];

         else{

             SamNode *r = &sam[++cnt] , *q = jp->son[x];

             *r = *q;

             r->l = r->nc = jp->l+;

             q->f = p->f = r;

             for( ; jp && jp->son[x]==q ; jp=jp->f) jp->son[x]=r;

         }

     }

 }

 void solve()

 {

     int len = strlen(str) , ret;

     for(int i= ; i<=cnt ; i++) num[sam[i].l]++;

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

     for(int i= ; i<=cnt ; i++) b[--num[sam[i].l]] = &sam[i];

     while(~scanf("%s" , str)){

         len = strlen(str) , ret=;

         SamNode *cur = root;

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

             int x = str[i]-'a';

             if(cur->son[x]){

                 ret++;

                 cur = cur->son[x];

             }

             else{

                 while(cur && !cur->son[x]) cur = cur->f;

                 if(!cur){

                     cur = root;

                     ret = ;

                 }else{

                     ret = cur->l+;

                     cur = cur->son[x];

                 }

             }

             cur->c = max(cur->c , ret);

         }

         for(int i=cnt ; i> ; i--){

             b[i]->nc = min(b[i]->nc , b[i]->c);

             //子节点可接受到的后缀父节点必定能够接收到，反之却不一定

             b[i]->f->c = max(b[i]->f->c , b[i]->c);

             b[i]->c = ;

         }

     }

 }

 int main() {

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

     scanf("%s" , str);

     init();

     int len = (int)strlen(str);

     for(int i= ; i<len ; i++) add(str[i]-'a');

     solve();

     int ret = ;

     SamNode *cur;

     for(int i= ; i<=cnt ; i++){

         cur = &sam[i];

         ret = max(cur->nc , ret);

     }

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

     return ;

 }