多个串的最长公共子串 SPOJ - LCS2 后缀自动机-白红宇

多个串的最长公共子串 SPOJ - LCS2 后缀自动机

阅读量：5030 次

发布时间：2019-06-12

本文共 2244 字，大约阅读时间需要 7 分钟。

题意：

求多个串的最长公共子串

这里用的是O(n)的后缀自动机写法

我后缀数组的专题有nlog(n)写法的

题解：

对于其中的一个串建立后缀自动机

然后对于后缀自动机上面的每一个节点求出每一个节点最长可以匹配的子串(用maxx【】数组存下)

但是在后缀自动机上面有些节点没有走过，但是是某些走过的点的父亲节点因此也是有值的

for (int i = tot; i; i--)     maxx[fail[i]] = max(maxx[fail[i]], min(len[fail[i]], maxx[i])); 然后求一个所有最小值里面的最大值就好了

1 #include 
      
         2 #include 
         3 #include 
        
           4 #include 
         
            5 #include 
          
             6 #include 
           
             7 #include 
            
              8 #include 
             
               9 #include 
              
                10 #include 
               
                 11 #include 
                
                  12 #include 
                 
                   13 #include 
                  
                    14 15 #define pi acos(-1.0) 16 #define eps 1e-9 17 #define fi first 18 #define se second 19 #define rtl rt<<1 20 #define rtr rt<<1|1 21 #define bug printf("******\n") 22 #define mem(a, b) memset(a,b,sizeof(a)) 23 #define name2str(x) #x 24 #define fuck(x) cout<<#x" = "<
                   
                    <
                    
                      maxx[i]) minn[i] = maxx[i];105 }106 107 } sam;108 109 110 int main() {111 #ifndef ONLINE_JUDGE112 FIN;113 #endif114 sfs(s);115 int n = strlen(s);116 sam.init();117 for (int i = 0; i < n; ++i) sam.extend((s[i] - 'a'));118 for (int i = 0; i <= sam.tot; i++) sam.minn[i] = -1;119 while (~sfs(s)) sam.match();120 int ans = 0;121 for (int i = 1; i <= sam.tot; i++) ans = max(ans, sam.minn[i]);122 printf("%d\n", ans);123 #ifndef ONLINE_JUDGE124 cout << "Totle Time : " << (double) clock() / CLOCKS_PER_SEC << "s" << endl;125 #endif126 return 0;127 }