Longest Common Substring（后缀自动机）
A string is finite sequence of characters over a non-empty finite set Σ.
In this problem, Σ is the set of lowercase letters.
SRE实战 互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。Substring, also called factor, is a consecutive sequence of characters occurrences at least once in a string.
Now your task is simple, for two 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 exactly two lines, each line consists of no more than 250000 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 Output: 3
n四次方的暴力不解释 = =‘
然后还有n方的dp
然后就是sa和sam
sa的复杂度是nlogn
然后就是sam了，玄学的复杂，完全不知道如何证明，o（玄学)就对了
1 #include<iostream>
2 #include<cstdio>
3 #include<queue>
4 #include<map>
5 #include<set>
6 #include<queue>
7 #include<algorithm>
8 #include<cmath>
9 #include<stack>
10 #include<cstring>
11 #define mem(a,b) memset(a,b,sizeof a)
12 #define sc(a) scanf("%d",&(a))
13 #define scc(a,b) scanf("%d %d",&(a),&(b))
14 #define ll long long
15 using namespace std; 16
17
18 int kd[1000000]; 19
20 struct dd 21 { 22
23 int fa,len; 24 int tr[29]; 25
26 }dian[1200000]; 27 int cnt[1200000]; 28
29 int last=1;int tot=1; 30 inline void add(int c) 31 { 32 int p=last; int np=last=++tot; 33 dian[np].len=dian[p].len+1; 34
35 for(;p&&!dian[p].tr[c];p=dian[p].fa)dian[p].tr[c]=np; 36 if(!p)dian[np].fa=1,cnt[1]++; 37 else
38 { 39 int q=dian[p].tr[c]; 40 if(dian[q].len==dian[p].len+1)dian[np].fa=q,cnt[q]++; 41 else
42 { 43 int nq=++tot; 44 dian[nq]=dian[q]; 45 dian[nq].len=dian[p].len+1; 46 dian[q].fa=dian[np].fa=nq; 47 cnt[nq]+=2; 48 for(;p&&dian[p].tr[c]==q;p=dian[p].fa)dian[p].tr[c]=nq; 49
50 } 51 } 52 } 53 int ans=0; 54 void top() 55 { 56 int now=1,t=0; 57 string s;cin>>s; int len = s.length(); 58 for(int i=0;i<len;i++) 59 { 60 int so=s[i]-'a'; 61 if(dian[now].tr[so])now=dian[now].tr[so],t++; 62 else
63 { 64 while(now&&!dian[now].tr[so])now=dian[now].fa; 65 if(!now)now=1,t=0; 66 else{ 67
68 t=dian[now].len+1; 69 //这里先对t赋值，因为这里是顺着fa向上走，到达的状态一定是两个串 70 //的公共字串，然后多了s【i】，t+=1;
71 now=dian[now].tr[so]; 72 } 73 } 74 ans=max(ans,t); 75 } 76 cout<<ans; 77 } 78
79 signed main() 80 { 81 string s; string t; 82 //ios::sync_with_stdio(0); 83 // cin.tie(0);
84
85 cin>>t; 86 s+=t; int n=s.length(); 87 for(int i=0;i<n;i++)add(s[i]-'a'); 88 top(); 89
90
91 }
更多精彩
