【GDOI2014 DAY2】Beyond （扩展KMP）

【题目】

【题意】

　　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;
		}
	}
}

代码如下：

  1 #include<cstdio>
  2 #include<cstdlib>
  3 #include<cstring>
  4 #include<iostream>
  5 #include<algorithm>
  6 using namespace std;
  7 #define Maxn 2000010
  8 
  9 int n;
 10 char s[2][Maxn];
 11 int nt[Maxn],td[2][Maxn];
 12 
 13 int c[Maxn];
 14 struct node
 15 {
 16     int x,y;
 17 }t[Maxn];
 18 
 19 bool cmp(node x,node y) {return x.y<y.y;}
 20 
 21 int mymax(int x,int y) {return x>y?x:y;}
 22 
 23 void get_nt(int x)
 24 {
 25     nt[1]=n;
 26     int mx=0,id;
 27     while(s[x][1+mx]==s[x][2+mx]&&mx<=n) mx++;
 28     nt[2]=mx;id=2;
 29     for(int i=3;i<=n;i++)
 30     {
 31         // mx=id+nt[id]-1;
 32         int now=nt[i-id+1];
 33         if(i+now-1<mx) nt[i]=now;//-> i+now<=mx 注意不要写成i+now-1<=mx!!!
 34         else
 35         {
 36             int j=mx-i+1;
 37             if(j<0) j=0;
 38             while(i+j<=n&&s[x][i+j]==s[x][1+j]) j++;
 39             nt[i]=j;
 40             id=i;mx=i+nt[i]-1;
 41         }
 42     }
 43 }
 44 
 45 void get_td(int x,int y)
 46 {
 47     int mx=0,id;
 48     while(s[x][1+mx]==s[y][1+mx]) mx++;
 49     td[y][1]=mx;id=1;
 50     for(int i=2;i<=n;i++)
 51     {
 52         int now=nt[i-id+1];
 53         if(i+now-1<mx) td[y][i]=now;
 54         else //i+now-1>=mx
 55         {
 56             int j=mx-i+1;
 57             if(j<0) j=0;
 58             while(i+j<=n&&s[x][1+j]==s[y][i+j]) j++;
 59             td[y][i]=j;
 60             id=i;mx=i+td[y][i]-1;
 61         }
 62     }
 63 }
 64 
 65 void add(int x,int y)
 66 {
 67     for(int i=x;i<=n;i+=i&(-i))
 68      c[i]+=y;
 69 }
 70 
 71 int get_sum(int x)
 72 {
 73     int ans=0;
 74     for(int i=x;i>=1;i-=i&(-i))
 75      ans+=c[i];
 76     return ans;
 77 }
 78 
 79 int ffind(int r)
 80 {
 81     int l=1;
 82     while(l<r)
 83     {
 84         int mid=(l+r)>>1;
 85         if(get_sum(r)-get_sum(mid)>0) l=mid+1;
 86         else r=mid;
 87     }
 88     if(get_sum(l)==0) return 0;
 89     return l;
 90 }
 91 
 92 int main()
 93 {
 94     scanf("%d",&n);
 95     scanf("%s%s",s[0]+1,s[1]+1);
 96     get_nt(0);get_td(0,1);
 97     
 98     get_nt(1);get_td(1,0);
 99     
100     memset(c,0,sizeof(c));
101     for(int i=1;i<=n;i++) 
102     {
103         t[i].x=i;
104         t[i].y=td[0][i];
105         add(i,1);
106     }
107     sort(t+1,t+1+n,cmp);
108     
109     
110     int now=1,ans=0;
111     for(int i=1;i<=n;i++)
112     {
113         while(t[now].y<i-1&&now<=n)
114         {
115             add(t[now].x,-1);
116             now++;
117         }
118         int x=ffind(td[1][i]+1);
119         if(x) ans=mymax(ans,x+i-2);
120     }
121     printf("%d
",ans);
122     return 0;
123 }

[BEYOND]

2016-08-20 10:55:34