Description
wyl8899今天也很刻苦的在做老师布置下来的题目！ 这一天老师布置的题目是这样的： 给出两个仅含小写字母的字符串A和B，输出最大的k，使得A[1..k]是B的子串。 A和B的长度都不会超过50000。 很显然他并不知道正确的做法，但是他居然卡着时间过掉了老师给的数据！ 你找到了他提交给老师的程序，经过测试你惊讶的发现，他的程序运行时间恰好是最终答案，单位是毫秒。 你现在找到了老师给的数据中的一笔，你决定至多修改A串中的一个字母，使得他的程序尽可能的慢。 现在，你能告诉我修改数据之后他的程序在这个测试点的运行时间么？（单位当然还是毫秒）
Input
两行，每行一个仅含小写字母的字符串，分别是A和B。 保证A和B的长度都不超过50000。
Output
你修改数据之后，wyl8899的程序在这个测试点的运行时间，单位是毫秒。
Sample Input
输入1： adbc aabbabd 输入2： aab aabcc
Sample Output
输出1： 3 输出2： 3
Data Constraint
保证A和B的长度都不超过50000。
Hint
数据是在Windows下生成的，测评环境是Linux。 由于换行符的差异，对于C/C++选手，请不要使用gets(s)读入一行字符，建议使用scanf("%s",s)的形式。 Pascal选手直接使用readln()读入一行即可，理论上readln()不会受到不同换行符的影响。
分析
发现可以枚举端点i，然后修改字符前的长度是len=LCP(B[i..m],A)
则ans=max(len+1+LCP(B[i+len+1..m],A[len+2..n]))
考场看到LCP时 心 肺 停 止
背完SA板子以后随便搞搞就欧克了
#include#include #include using namespace std;const int N=1e6+10;int n,n1,n2,m;int c[N],x[N],y[N],sa[N],rk[N],height[(1<<21)+1][21],pow[21],ans;char s[N],s2[N];int MIN(int l,int r) { if (l>r) swap(l,r); l++; int ans=2147483647; for (int k=20;k>=0;k--) if (l+pow[k]-1<=r) { ans=min(ans,height[l][k]); l+=pow[k]; } return ans;}void Solve() { int len,l; for (int i=1;i<=n2;i++) { len=min(min(n1,n2-i+1),MIN(rk[i],rk[n2+1])); ans=max(ans,min(min(n1,n2-i+1),len+1)); ans=max(ans,min(min(n1,n2-i+1),len)); l=min(min(n1,n2-i+1)-len-1,MIN(rk[i+len+1],rk[n2+len+2])); ans=max(ans,len+1+l); }}void SA() { memset(c,0,sizeof c); for (int i=1;i<=n;i++) c[x[i]=s2[i]]++; for (int i=1;i<=m;i++) c[i]+=c[i-1]; for (int i=n;i;i--) sa[c[x[i]]--]=i; for (int k=1;k<=n;k<<=1) { memset(c,0,sizeof c);int cnt=0; for (int i=n-k+1;i<=n;i++) y[++cnt]=i; for (int i=1;i<=n;i++) if (sa[i]>k) y[++cnt]=sa[i]-k; for (int i=1;i<=n;i++) c[x[i]]++; for (int i=1;i<=m;i++) c[i]+=c[i-1]; for (int i=n;i;i--) sa[c[x[y[i]]]--]=y[i],y[i]=0; swap(x,y);cnt=0; x[sa[1]]=++cnt; for (int i=2;i<=n;i++) x[sa[i]]=(y[sa[i]]==y[sa[i-1]]&&y[sa[i]+k]==y[sa[i-1]+k])?cnt:++cnt; if (cnt==n) break; m=cnt; }}void Get_Height() { for (int i=1;i<=n;i++) rk[sa[i]]=i; int k=0; for (int i=1;i<=n;i++) { if (rk[i]==1) continue; k=max(0,k-1); int j=sa[rk[i]-1]; while (s2[j+k]==s2[i+k]&&i+k<=n&&j+k<=n) k++; height[rk[i]][0]=k; }}void RMQ() { for (int k=1;k<=20;k++) for (int i=1;i<=n;i++) height[i][k]=min(height[i][k-1],height[i+pow[k-1]][k-1]);}int main() { scanf("%s",s+1);scanf("%s",s2+1); n1=strlen(s+1);n=strlen(s2+1);m='z';n2=n; for (int i=n+1;i<=n1+n;i++) s2[i]=s[i-n]; n+=n1; pow[0]=1; for (int i=1;i<=20;i++) pow[i]=pow[i-1]<<1; SA();memset(height,0x7f,sizeof height); Get_Height(); RMQ(); Solve(); printf("%d",ans);}