Longest Common Substring II SPOJ - LCS2

太过爱你忘了你带给我的痛 2021-12-10 10:43 106阅读 0赞

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，然后另外一个串在上面跑，如果可以跑下去，匹配长度就加一，否则就不断沿着父亲边回去，直到跟节点或者找到了可以跑下去的边，如果找到了可以跑下去的边，此时的匹配长度就是当前的节点p里面最长的串+1, p有可以跑下去的边。 **

**现在换成了多个串找公共子串，我们还是采用同样的方法，第一个串建立sam，剩下的每个串都去上面跑，我们要记录每个节点可以匹配的最大长度。注意， 如果当前走到p点的匹配长度是tmp，那么p的父亲和祖先的匹配长度一定是他们的最长串。 这个也要去更新维护，因为其他的串可能走不到p，但是可以走到p的祖先。 **

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 #include<bits/stdc++.h>
     2 using namespace std;  
     3 int const N=200000+1000;  
     4 struct node{
     5     int len,fa,ch[26];  
     6 }a[N<<1];  
     7 char s[N];   
     8 int tot,ls,f[11][N<<1],n,num[N],sa[N<<1];  
     9 void add(int c){
    10     int p=ls;  
    11     int np=ls=++tot; 
    12     a[np].len=a[p].len+1;  
    13     for(; p&& !a[p].ch[c];p=a[p].fa) a[p].ch[c]=np;  
    14     if(!p) a[np].fa=1;  
    15     else {
    16         int q=a[p].ch[c];  
    17         if(a[q].len==a[p].len+1)  a[np].fa=q;  
    18         else {
    19             int nq=++tot; a[nq]=a[q];  
    20             a[nq].len=a[p].len+1;  
    21             a[q].fa=a[np].fa=nq;  
    22             for(;p && a[p].ch[c]==q;p=a[p].fa) a[p].ch[c]=nq;  
    23         }
    24     } 
    25 } 
    26 void solve(){
    27     int p=1,tmp=0;    
    28     for(int i=0;s[i];i++){
    29         int c=s[i]-'a';           
    30         if(a[p].ch[c]) p=a[p].ch[c],tmp++;  
    31         else {  
    32             while (p && !a[p].ch[c])  p=a[p].fa;
    33             if(!p) p=1,tmp=0;  
    34             else  tmp=a[p].len+1,p=a[p].ch[c];  
    35         }  
    36         f[n][p]=max(f[n][p],tmp);   
    37     }  
    38     for(int i=tot;i>=1;i--){ 
    39         int x=sa[i]; 
    40         int p=a[x].fa; 
    41         if(!f[n][x]) continue;   
    42         while (p && a[p].len!=f[n][p]){
    43             f[n][p]=a[p].len;  
    44             p=a[p].fa; 
    45         }  
    46     }        
    47 }       
    48 int main(){
    49     tot=ls=1; 
    50     scanf("%s",s);      
    51     for(int i=0;s[i];i++)  
    52         add(s[i]-'a');  
    53     int len=strlen(s);  
    54     for(int i=1;i<=tot;i++) num[a[i].len]++;  
    55     for(int i=1;i<=len;i++) num[i]+=num[i-1];  
    56     for(int i=1;i<=tot;i++) sa[num[a[i].len]--]=i;    
    57     while (scanf("%s",s)!=EOF){
    58         n++;  
    59         solve();  
    60     }
    61     int ans=0;  
    62     for(int i=1;i<=tot;i++) {
    63         int tmp=a[i].len; 
    64         for(int j=1;j<=n;j++)  
    65             tmp=min(tmp,f[j][i]);  
    66         ans=max(ans,tmp);     
    67     }  
    68     printf("%d\n",ans); 
    69     return 0; 
    70 }

转载于:https://www.cnblogs.com/ZJXXCN/p/11043008.html

[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20211210/1db3cf993c73497d86fbbcf97bac4fd6.png