(http://acm.hust.edu.cn/vjudge/contest/view.action?cid=105904#problem/E)
题意:给定字符串A,B,int K。问存在多少个(i,j,k)满足A(i,i+k)=B(j,j+k) && k>=K。
解法:把A构造后缀自动机,然后求出right数组。一开始不知道怎么topo排序,看了别人的博客才知道由这个简单的topo方法。然后用p的right值,更新pre[p]的right值。有一个问题是,当B在进行lcp的时候,找到了p,不光是匹配到了p,还匹配到了pre[p]..所以要预处理出pre[p]..的答案,因为从pre[p]开始A肯定是完全匹配。
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <queue>
//#include <tr1/unordered_set>
//#include <tr1/unordered_map>
#include <bitset>
//#pragma comment(linker, "/STACK:1024000000,1024000000")
using namespace std;
#define lson l, m, rt<<1
#define rson m+1, r, rt<<1|1
#define inf 1e9
#define debug(a) cout << #a" = " << (a) << endl;
#define debugarry(a, n) for (int i = 0; i < (n); i++) { cout << #a"[" << i << "] = " << (a)[i] << endl; }
#define clr(x, y) memset(x, y, sizeof x)
#define ll long long
#define ull unsigned long long
#define FOR(i,a,b) \
for(i=a;a<b?i<=b:i>=b;a<b?i++:i--)
const int maxn = +;
struct suffix_automaton{
int tonum(char c)
{
if(c>='a'&&c<='z') return c-'a';
else return c-'A'+;
}
int son[maxn][],pre[maxn],step[maxn];
int last,si;
int right[maxn];
void pushback(int v){
step[++si]=v;
pre[si]=-;
clr(son[si],-);
}
void Extend(int ch)
{
pushback(step[last]+);
int p=last,np=si;
while(p!=-&&son[p][ch]==-)
son[p][ch]=np,
p=pre[p];
if(p==-) pre[np]=;
else{
int q=son[p][ch];
if(step[q]==step[p]+) pre[np]=q;
else{
pushback(step[p]+);
int nq=si;
memcpy(son[nq],son[q],sizeof son[q]);
pre[nq]=pre[q];
pre[q]=pre[np]=nq;
while(p!=-&&son[p][ch]==q)
son[p][ch]=nq,
p=pre[p];
}
}
last=np;
}
void init()
{
si=last=;
clr(son[],-);
pre[]=-;
step[]=;
}
int cnt[maxn],id[maxn];
void ccv()
{
clr(cnt,);
for(int i=;i<=si;i++)
cnt[step[i]]++;
for(int i=;i<=si;i++)
cnt[i]+=cnt[i-];
for(int i=;i<=si;i++)
id[--cnt[step[i]]]=i;
}
void cca(char *s)
{
ccv();
int p=;
clr(right,);
for(int i=;s[i];i++)
{
right[son[p][ tonum(s[i]) ]]=;
p=son[p][tonum(s[i])];
}
for(int i=si;i>=;i--) if(pre[id[i]]!=-)
right[pre[id[i]]]+=right[id[i]];
right[]=;
}
ll la[maxn];
ll solve(int k,char *b)
{
clr(la,);
for(int i=;i<=si;i++)
{
int j=id[i];
if(pre[j]!=-)
la[j] = (ll)max(,step[j]-max(step[pre[j]]+,k)+)*right[j],
la[j] += la[pre[j]];
else
la[j] = (ll)max(,step[j]-k+)*right[j];
// printf("j %d ri %d la %lld\n",j,right[j],la[j]);
}
ll ans=;
int j=,l=;
for(int i=;b[i];i++)
{
int c=tonum(b[i]);
while(j!=-&&son[j][c]==-)
j=pre[j],l=j==-?:min(l,step[j]);
if( j != - )
{
j=son[j][c];
l++;
ll t;
if(pre[j]!=-)
ans += t = (ll)max(,l-max(step[pre[j]]+,k)+) * right[j] + la[pre[j]];
else ans += t = (ll)max(,l-k+) * right[j];
}else j=;
}
return ans;
}
}su;
char a[maxn],b[maxn];
int main()
{
// freopen("input.txt","r",stdin);
int k;
while(~scanf("%d",&k))
{
if(!k) break;
scanf("%s%s",a,b);
su.init();
for(int i=;a[i];i++)
su.Extend(su.tonum(a[i]));
su.cca(a);
ll ans = su.solve(k,b);
printf("%I64d\n",ans);
}
return ;
}