【题目】
【题意】
Jodie和Aiden在做游戏。Jodie在一个长度为l字符串环上走路，他每离开一个就会记下格子当前字符。他让Aiden在他走了一圈后叫他停下来。Aiden决定耍一下Jodie，在他走了k步重复的格后才告诉他。Jodie离开的格子会随机变为一个字符。Jodie走了两次(起点可能不同)，每次都走了n(即l+k)步。给出两个长度n的字符串，表示Jodie两次记录的字符串，问l最大可以是多少。 N<=100000
【分析】
做2次扩展KMP，枚举第二个串的第i位与第一个串对应。一开始容易走入的误区就是直接使用tend2[i]然后判断，但是我们其实不一定让i往后的串越长越好，因为可能前面匹配不了。但是可以确定的是前面的匹配长度已经固定了，即i-1，所以我们只要在第一个串中找到所有的tend1大于等于i-1的x，当x越大，匹配长度越大，所以我们找最大的x使得其tend1[x]大于等于i-1。 可以用二分+rmq或者线段树。 也可以一开始排个序，然后用树状数组动态加减，然后用二分查找。
再放一次扩展KMP部分的代码：（注意那个小于号和小于等于号那里！很重要！）：
void get_nt(int x)
{
nt[1]=n;
int mx=0,id;
while(s[x][1+mx]==s[x][2+mx]&&mx<=n) mx++;
nt[2]=mx;id=2;
for(int i=3;i<=n;i++)
{
int now=nt[i-id+1];
if(i+now-1<mx) nt[i]=now;//-> i+now<=mx 注意不要写成i+now-1<=mx!!!
else
{
int j=mx-i+1;
if(j<0) j=0;
while(i+j<=n&&s[x][i+j]==s[x][1+j]) j++;
nt[i]=j;
id=i;mx=i+nt[i]-1;
}
}
} void get_td(int x,int y)
{
int mx=0,id;
while(s[x][1+mx]==s[y][1+mx]) mx++;
td[y][1]=mx;id=1;
for(int i=2;i<=n;i++)
{
int now=nt[i-id+1];
if(i+now-1<mx) td[y][i]=now;
else //i+now-1>=mx
{
int j=mx-i+1;
if(j<0) j=0;
while(i+j<=n&&s[x][1+j]==s[y][i+j]) j++;
td[y][i]=j;
id=i;mx=i+td[y][i]-1;
}
}
}
代码如下：
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
#define Maxn 2000010 int n;
char s[][Maxn];
int nt[Maxn],td[][Maxn]; int c[Maxn];
struct node
{
int x,y;
}t[Maxn]; bool cmp(node x,node y) {return x.y<y.y;} int mymax(int x,int y) {return x>y?x:y;} void get_nt(int x)
{
nt[]=n;
int mx=,id;
while(s[x][+mx]==s[x][+mx]&&mx<=n) mx++;
nt[]=mx;id=;
for(int i=;i<=n;i++)
{
// mx=id+nt[id]-1;
int now=nt[i-id+];
if(i+now-<mx) nt[i]=now;//-> i+now<=mx 注意不要写成i+now-1<=mx!!!
else
{
int j=mx-i+;
if(j<) j=;
while(i+j<=n&&s[x][i+j]==s[x][+j]) j++;
nt[i]=j;
id=i;mx=i+nt[i]-;
}
}
} void get_td(int x,int y)
{
int mx=,id;
while(s[x][+mx]==s[y][+mx]) mx++;
td[y][]=mx;id=;
for(int i=;i<=n;i++)
{
int now=nt[i-id+];
if(i+now-<mx) td[y][i]=now;
else //i+now-1>=mx
{
int j=mx-i+;
if(j<) j=;
while(i+j<=n&&s[x][+j]==s[y][i+j]) j++;
td[y][i]=j;
id=i;mx=i+td[y][i]-;
}
}
} void add(int x,int y)
{
for(int i=x;i<=n;i+=i&(-i))
c[i]+=y;
} int get_sum(int x)
{
int ans=;
for(int i=x;i>=;i-=i&(-i))
ans+=c[i];
return ans;
} int ffind(int r)
{
int l=;
while(l<r)
{
int mid=(l+r)>>;
if(get_sum(r)-get_sum(mid)>) l=mid+;
else r=mid;
}
if(get_sum(l)==) return ;
return l;
} int main()
{
scanf("%d",&n);
scanf("%s%s",s[]+,s[]+);
get_nt();get_td(,); get_nt();get_td(,); memset(c,,sizeof(c));
for(int i=;i<=n;i++)
{
t[i].x=i;
t[i].y=td[][i];
add(i,);
}
sort(t+,t++n,cmp); int now=,ans=;
for(int i=;i<=n;i++)
{
while(t[now].y<i-&&now<=n)
{
add(t[now].x,-);
now++;
}
int x=ffind(td[][i]+);
if(x) ans=mymax(ans,x+i-);
}
printf("%d\n",ans);
return ;
}
[BEYOND]
2016-08-20 10:55:34