Description
If a string is in the form UVU, where U is not empty, and V has exactly L characters, we say UVU
is an L-Gap string. For example, abcbabc is a 1-Gap string. xyxyxyxyxy is both a 2-Gap string
and also a 6-Gap string, but not a 10-Gap string (because U is non-empty).
Given a string s, and a positive integer g, you are to find the number of g-Gap substrings in s. s
contains lower-case letters only, and has at most 50,000 characters.Input
The first line contains a single integer t (1 ≤ t ≤ 10), the number of test cases. Each of the t followings
contains an integer g (1 ≤ g ≤ 10) followed by a string s.Output
For each test case, print the case number and the number of g-Gap substrings. Look at the output for
sample input for details.Sample Input
2
1 bbaabaaaaa
5 abxxxxxabSample Output
Case 1: 7
Case 2: 1
【题意】
UVU形式的串的个数，V的长度规定，U要一样，位置不一样即为不同字串
【分析】
表示做了poj3693还是不会做这题。
为什么会想到枚举L然后分块呢？？？？
为什么呢？？？？
这种方法于我而言还是有点难理解的啊。
主要是分块!!
任意一个满足条件的UVU，假设U的长度是len，那么左端的U必然包含按照len切分的T串的某个字串，及0，len，2len，3len...。（这点要仔细想清楚）
那么枚举每个端点i*len，然后利用RMQ求后缀i*len和后缀i*len+L+len的LCP，然后字符串T反向，再求一遍反向的LCP2。（其中LCP要小于等于len，否则会重复，仔细想清楚）
最后累加求和sum+=(LCP+LCP2-1)-len+1。（这点想清楚为什么是-len）
blog：http://blog.csdn.net/u011526463/article/details/14000693
还有，其实，貌似不用后缀数组直接两个while前后就可以了。时间貌似还是nlogn的。 【（2017-03-24 14:43:33）许多年后发现以前在搞笑。。】
代码如下：
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
#define Maxl 100010 int l,len;
char s[Maxl];
int c[Maxl],cl; int mymin(int x,int y) {return x<y?x:y;} void init()
{
scanf("%d%s",&l,s);
len=strlen(s);
cl=;
for(int i=;i<len;i++) c[++cl]=s[i]-'a'+;
} int sa[Maxl],rk[Maxl],y[Maxl],wr[Maxl],Rs[Maxl];
void get_sa(int m)
{
memcpy(rk,c,sizeof(rk));
for(int i=;i<=m;i++) Rs[i]=;
for(int i=;i<=cl;i++) Rs[rk[i]]++;
for(int i=;i<=m;i++) Rs[i]+=Rs[i-];
for(int i=cl;i>=;i--) sa[Rs[rk[i]]--]=i; int ln=,p=;
while(p<cl)
{
int k=;
for(int i=cl-ln+;i<=cl;i++) y[++k]=i;
for(int i=;i<=cl;i++) if(sa[i]>ln) y[++k]=sa[i]-ln;
for(int i=;i<=cl;i++) wr[i]=rk[y[i]]; for(int i=;i<=m;i++) Rs[i]=;
for(int i=;i<=cl;i++) Rs[wr[i]]++;
for(int i=;i<=m;i++) Rs[i]+=Rs[i-];
for(int i=cl;i>=;i--) sa[Rs[wr[i]]--]=y[i]; for(int i=;i<=cl;i++) wr[i]=rk[i];
for(int i=cl+;i<=cl+ln;i++) wr[i]=;
p=,rk[sa[]]=;
for(int i=;i<=cl;i++)
{
if(wr[sa[i]]!=wr[sa[i-]]||wr[sa[i]+ln]!=wr[sa[i-]+ln]) p++;
rk[sa[i]]=p;
}
ln*=,m=p;
}
sa[]=rk[]=;
} int height[Maxl];
void get_he()
{
int k=;
for(int i=;i<=cl;i++) if(rk[i]!=)
{
int j=sa[rk[i]-];
if(k) k--;
while(c[i+k]==c[j+k]&&i+k<=cl&&j+k<=cl) k++;
height[rk[i]]=k;
}
} int d[Maxl][];
void rmq_init()
{
for(int i=;i<=cl;i++) d[i][]=height[i];
for(int j=;(<<j)<=cl;j++)
for(int i=;i+(<<j)-<=cl;i++)
d[i][j]=mymin(d[i][j-],d[i+(<<j-)][j-]);
} int rmq(int x,int y)
{
int t;x=rk[x];y=rk[y];
if(x>y) t=x,x=y,y=t;
x++;
int k=;
while((<<k+)<=y-x+) k++;
return mymin(d[x][k],d[y-(<<k)+][k]);
} void ffind()
{
int ans=;
for(int i=;i<=cl;i++)
{
for(int j=;j<=cl/i;j++)
{
int now=j*i+,x,y=;
if(c[now]!=c[now+l+i]||now+l+i>cl) continue;
x=mymin(i,rmq(now,now+l+i));//向后匹配
while(c[now-y-]==c[now+l+i-y-]&&y+<i) y++;//向前匹配
if(x+y-i+>) ans+=x+y-i+;
}
}
printf("%d\n",ans);
} int main()
{
int T,kase=;
scanf("%d",&T);
while(T--)
{
init();
get_sa();
get_he();
rmq_init();
printf("Case %d: ",++kase);
ffind();
}
return ;
}
[UVA10829]
2016-07-19 15:44:08
这道题我看了100遍！！
现在又明白了一点了ORZ。。。分块屌ORZ。。。
好吧，是按照u的长度分块！！
为什么呢，目的是：答案串的u至少包含一个分割点（上面的蓝色突起）
我们对于其包含的第一个分割点时计算他！！！（就是上面红色圈起的部分）
如果匹配长度越过第二个分割点，那么是会重复计算的，所以在这一题，向前匹配和向后匹配都可以直接while，越过分割点的时候就结束。
ORZ。。。
2016-11-13 14:52:25