Common SubstringsDescription
A substring of a string T is defined as:
T(i, k)=TiTi+1...Ti+k-1, 1≤i≤i+k-1≤|T|.
Given two strings A, B and one integer K, we define S, a set of triples (i, j, k):
S = {(i, j, k) | k≥K, A(i, k)=B(j, k)}.
You are to give the value of |S| for specific A, B and K.
Input
The input file contains several blocks of data. For each block, the first line contains one integer K, followed by two lines containing strings A and B, respectively. The input file is ended by K=0.
1 ≤ |A|, |B| ≤ 105
1 ≤ K ≤ min{|A|, |B|}
Characters of A and B are all Latin letters.Output
For each case, output an integer |S|.
Sample Input
2
aababaa
abaabaa
1
xx
xx
0Sample Output
22
5
【题意】
给两个长度不超过100000的字符串A和B, 求三元组(i, j, k)的数量, 即满足A串从i开始的后缀与B串从j开始的后缀有长度为k的公共前缀, 还要求k不小于某个给你的数K.
【分析】
如果i后缀与j后缀的LCP长度为L, 在L不小于K的情况下, 它对答案的贡献为L - K + 1.
所以问题就是快速求出两个串的后缀的LCP。
就要用到后缀数组，把两个串拼成一个串，中间加一个特殊字符，然后做后缀数组。
求出height数组后根据k分组（min大于等于k的分在一组），同一组的LCP一定大于等于k。（height数组的性质啦，这个很基本）
接下来就是求出sum｛L-K+1｝，如果直接暴力的话for2遍加一个RMQ也很慢。
然后看到大神们说用什么单调栈，哦~~ 单调的优美性质！！！
可以分成两步求，先求B串在下，A串在上的ans。再反过来求一遍。
过程好像比较难说清楚。
反正...对于B串上面的一堆A串，因为LCP是求min，所以LCP必定是单调递增，所以像下图那样做：
开了三个数组，s表示其单位贡献值，cnt表示有多少个A串是这个贡献值，h为从当前位置到底部的cnt*s的和（h便于计算的）。
然后就更新和替换。遇到一个B串就把h[tp]累加到ans中即可。
反过来做也是一样的。
单调！！单调！！单调哦！！
好像很厉害！！
主要看代码~~
还有，这道题是有大写字母的！！！坑的我RE了巨久！！
还有记得long long！！
代码如下：
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
#define INF 0xfffffff
#define Maxl 200010
#define LL long long int k,la;
char a[Maxl],b[Maxl];
int c[Maxl];
int cl; int sa[Maxl],rank[Maxl],Rs[Maxl],wr[Maxl],y[Maxl];
//sa -> 排名第几的是谁
//rank -> i的排名
//Rs数值小于等于i的有多少个
//y -> 第二关键字排名第几的是谁（类似sa）
int height[Maxl]; void get_sa(int m)
{
memcpy(rank,c,sizeof(rank));
for(int i=;i<=m;i++) Rs[i]=;
for(int i=;i<=cl;i++) Rs[rank[i]]++;
for(int i=;i<=m;i++) Rs[i]+=Rs[i-];
for(int i=cl;i>=;i--) sa[Rs[rank[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]=rank[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]=rank[i];
for(int i=cl+;i<=cl+ln;i++) wr[i]=;
p=;rank[sa[]]=;
for(int i=;i<=cl;i++)
{
if(wr[sa[i]]!=wr[sa[i-]]||wr[sa[i]+ln]!=wr[sa[i-]+ln]) p++;
rank[sa[i]]=p;
}
m=p,ln*=;
}
sa[]=rank[]=;
} void get_he()
{
int kk=;
for(int i=;i<=cl;i++)
{
// if(rank[i]==1) break;
int j=sa[rank[i]-];
if(kk) kk--;
while(c[i+kk]==c[j+kk]&&i+kk<=cl&&j+kk<=cl) kk++;
height[rank[i]]=kk;
}
} LL h[Maxl],cnt[Maxl],s[Maxl];
int tp;
void ffind()
{
LL ans=;tp=;
s[]=INF;
//******
for(int i=;i<=cl-;i++)
{
if(sa[i]>=la+) //B串
ans+=h[tp];
if(height[i+]-k+<s[tp])//替换
{
LL sum=;
while(height[i+]-k+<=s[tp]&&tp) sum+=cnt[tp--];
s[++tp]=(height[i+]-k+),cnt[tp]=sum,h[tp]=h[tp-]+cnt[tp]*s[tp];
}
else s[++tp]=height[i+]-k+,cnt[tp]=,h[tp]=h[tp-];
if(sa[i]<=la) cnt[tp]++,h[tp]+=s[tp];//A串
if(height[i+]<k)
{
tp=;s[]=INF;
}
}tp=;s[tp]=INF;
for(int i=;i<=cl-;i++)
{
if(sa[i]<=la) //A串
ans+=h[tp];
if(height[i+]-k+<s[tp])//替换
{
LL sum=;
while(height[i+]-k+<=s[tp]&&tp) sum+=cnt[tp--];
s[++tp]=(height[i+]-k+),cnt[tp]=sum,h[tp]=h[tp-]+cnt[tp]*s[tp];
}
else s[++tp]=height[i+]-k+,cnt[tp]=,h[tp]=h[tp-];
if(sa[i]>=la+) cnt[tp]++,h[tp]+=s[tp];//B串
if(height[i+]<k)
{
tp=;s[tp]=INF;
}
}
printf("%I64d\n",ans);
} void init()
{
scanf("%s%s",a,b);
int l=strlen(a);cl=;
la=l;
for(int i=;i<l;i++)
{
if(a[i]>='a'&&a[i]<='z') c[++cl]=a[i]-'a'+;
else c[++cl]=a[i]-'A'+;
}
c[++cl]=;
l=strlen(b);
for(int i=;i<l;i++)
{
if(b[i]>='a'&&b[i]<='z') c[++cl]=b[i]-'a'+;
else c[++cl]=b[i]-'A'+;
}
} int main()
{
while()
{
scanf("%d",&k);
if(k==) break;
init();
get_sa();
get_he();
ffind();
}
return ;
}
[POJ3415]
2016-07-17 15:00:50
update： 哈哈学了SAM的我回来更新这道题啦！！ 然而很搞笑的是...我打的SAM其实跟后缀数组差不多长！！ 而且蒟蒻表示调试了很久！狗带！！SAM太难调了！！ 好吧我一开始想不出来..是因为·不太懂那个SAM上某个点表示的串究竟是什么~~ 其实是一个连续的区间，记为min(x)~max(x)（这是长度）, 其中min(x)=step[pre[x]]+1,max(x)=step[x]... 为什么呢..其实SAM就是省掉了重复子串吧，我觉得~~
比如说上面这个，parent最大串一定是他的后缀来的，后面那个b表示的后缀其实有aab、ab、b、xaab....
但是aab、ab、b明显他的parent也有，就不会用后面那个来表示，
所以最短的都有step[pre[x]]+1那么长而且到时如果还要表示aab-----的串的话，其实信息也是保存到parent那里了。（大概，意会一下~） 关于这道题，我们处理的目标是前缀的后缀~（上面用后缀数组的方法处理的是后缀的前缀，都叫后缀xx其实怎么我觉得是反过来的呢~）
用A串建机，B串跑。 跑法有点类似AC自动机上的跑法，跑出来的长度啊都是让后缀匹配最长的！！ 我们知道如果有长度大于k的子串s和ss，如过ss是s的子串，而且s合法（就是在A串出现），那么ss也合法，而且ss的答案一定大于等于s的答案。 我一开始就是不知道怎么弄ss多余部分的答案。
很容易想到就是用rt[x]*(length-k+1),但是直接减的话，你算一些小的串，其实x并不能代表这个串，就是说你现在扫到的位置不一定是这个小串的首位置，那么直接用right数组就会有问题，就会漏解。
上面说了，x表示的串为min(x)~max（x），我们就在x的位置先算他表示的串，然后在parent那里打标记，用parent的right数组来算，就可以避免这种问题。
具体怎么做看GDXB讲解：先对第一个串构造 SAM,逆拓扑序求出right存入r[]。
某个节点的right集合表示Min(x)~Max(x)这一段子串都出现了r[x]次！
用第二个串对 SAM 做 LCS，当前节点x LCS>=K时，ans+=ans+=r[x]*(len-maxx(k,step[pre[x]]+1)+1);（当前匹配的最长串的子串数）。如果step[pre[x]]>=k,cnt[pre[x]]++;
拓扑序逆序统计不是最长公共子串的状态但是被子串包含的个数，ans+=cnt[p]*(step[p]- max(K,Min(p)+1)*r[p]，同时维护cnt:cnt[pre[p]]+=cnt[p]。
说一说right数组怎么求，因为我这个一开始都打错了！！
right[x]表示x这个点表示的串在原串出现多少次。
我们把主链上的right全部清成1，然后按拓扑序把i的答案放到pre[i]上即可。
代码如下：(SAM)
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<queue>
#include<cmath>
using namespace std;
#define Maxn 100010
#define LL long long char s[Maxn],ss[Maxn];
int len,ml;
LL lim; LL ans;
LL mymax(LL x,LL y) {return x>y?x:y;} struct node
{
int tot,pre[*Maxn],son[*Maxn][];
LL step[*Maxn],rt[*Maxn],cnt[*Maxn];
int last;
void extend(int k)
{
int np=++tot,p=last;
step[np]=step[last]+;
rt[np]=;
while(p&&!son[p][k])
{
son[p][k]=np;
p=pre[p];
}
if(!p) pre[np]=;
else
{
int q=son[p][k];
if(step[q]==step[p]+) pre[np]=q;
else
{
int nq=++tot;
step[nq]=step[p]+;
memcpy(son[nq],son[q],sizeof(son[nq]));
pre[nq]=pre[q];
pre[q]=pre[np]=nq;
while(p&&son[p][k]==q)
{
son[p][k]=nq;
p=pre[p];
}
}
}
last=np;
}
void init()
{
memset(pre,,sizeof(pre));
memset(son,,sizeof(son));
memset(rt,,sizeof(rt));
memset(cnt,,sizeof(cnt));
}
void build()
{
step[]=;tot=;
last=;
for(int i=;i<=len;i++)
{
int k=s[i]-'a'+;
if(k<) k=s[i]-'A'+;
extend(k);
}
}
int aq[*Maxn],tp[*Maxn],Rs[*Maxn];
void get_tp()
{
for(int i=;i<=tot;i++) Rs[i]=;
for(int i=;i<=tot;i++) Rs[step[i]]++;
for(int i=;i<=tot;i++) Rs[i]+=Rs[i-];
for(int i=;i<=tot;i++) tp[Rs[step[i]]--]=i;
}
void get_rt()
{
int now=;
for(int i=tot;i>=;i--) rt[pre[tp[i]]]+=rt[tp[i]];
}
void ffind()
{
get_tp();
get_rt();
int now=,sp=;
ans=;
for(int i=;i<=ml;i++)
{
int k=ss[i]-'a'+;
if(k<) k=ss[i]-'A'+;
while(now&&!son[now][k]) now=pre[now],sp=step[now];
if(son[now][k]) now=son[now][k],sp++;
else now=,sp=;
if(sp>=lim) ans+=(sp-mymax(lim,step[pre[now]]+)+)*rt[now];
if(lim<step[pre[now]]+) cnt[pre[now]]++;
}
for(int i=tot;i>=;i--)
cnt[pre[tp[i]]]+=cnt[tp[i]];
for(int i=;i<=tot;i++) if(step[i]>=lim)
ans+=rt[i]*cnt[i]*(step[i]-mymax(step[pre[i]]+,lim)+); for(int i=;i<=tot;i++) pre[i]=;
for(int i=;i<=tot;i++)
for(int j=;j<=;j++) son[i][j]=;
for(int i=;i<=tot;i++) rt[i]=;
for(int i=;i<=tot;i++) cnt[i]=;
} }suf; int main()
{
suf.init();
while()
{
scanf("%lld",&lim);
if(lim==) break;
scanf("%s%s",s+,ss+);
len=strlen(s+);
ml=strlen(ss+);
suf.build();
suf.ffind();
printf("%lld\n",ans);
}
return ;
}
[POJ3415]
记得long long~
2016-09-16 11:47:27
更新