Common Substrings
Time Limit: 5000MS | Memory Limit: 65536K | |
Total Submissions: 6409 | Accepted: 2117 |
Description
A substring of a string T is defined as:
Given two strings A, B and one integer K, we defineS, a set of triples (i, j, k):
You are to give the value of |S| for specific A, B andK.
Input
The input file contains several blocks of data. For each block, the first line contains one integerK, followed by two lines containing strings A and B, respectively. The input file is ended byK=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 0
Sample Output
22 5
题意:已知两个字符串,求有多少个长度不小于k的公共子串。
解题思路:后缀数组+单调栈优化,
代码:
/* *********************************************** Author :xianxingwuguan Created Time :2014-1-29 15:31:23 File Name :2.cpp ************************************************ */ #pragma comment(linker, "/STACK:102400000,102400000") #include <stdio.h> #include <string.h> #include <iostream> #include <algorithm> #include <vector> #include <queue> #include <set> #include <map> #include <string> #include <math.h> #include <stdlib.h> #include <time.h> using namespace std; const int maxn=400030; int sa[maxn],rank[maxn],height[maxn],c[maxn],t1[maxn],t2[maxn]; void da(int *str,int n,int m) { int i,j,k,p,*x=t1,*y=t2; for(i=0;i<m;i++)c[i]=0; for(i=0;i<n;i++)c[x[i]=str[i]]++; for(i=1;i<m;i++)c[i]+=c[i-1]; for(i=n-1;i>=0;i--)sa[--c[x[i]]]=i; for(k=1;k<=n;k<<=1) { p=0; for(i=n-k;i<n;i++)y[p++]=i; for(i=0;i<n;i++)if(sa[i]>=k)y[p++]=sa[i]-k; for(i=0;i<m;i++)c[i]=0; for(i=0;i<n;i++)c[x[y[i]]]++; for(i=1;i<m;i++)c[i]+=c[i-1]; for(i=n-1;i>=0;i--)sa[--c[x[y[i]]]]=y[i]; swap(x,y); p=1;x[sa[0]]=0; for(i=1;i<n;i++) x[sa[i]]=y[sa[i]]==y[sa[i-1]]&&y[sa[i]+k]==y[sa[i-1]+k]?p-1:p++; if(p>=n)break; m=p; } } void calheight(int *str,int n) { int i,j,k=0; for(i=0;i<=n;i++)rank[sa[i]]=i; for(i=0;i<n;i++) { if(k)k--; j=sa[rank[i]-1]; while(str[i+k]==str[j+k])k++; height[rank[i]]=k; } } char s1[maxn],s2[maxn]; int str[maxn]; int a[maxn],b[maxn],f[maxn]; int main() { //freopen("data.in","r",stdin); //freopen("data.out","w",stdout); int i,j,k,m,n; while(~scanf("%d",&k)) { if(k==0)break; scanf("%s",s1);scanf("%s",s2); int l1=strlen(s1),l2=strlen(s2); int len=0; for(i=0;i<l1;i++)str[len++]=s1[i]; str[len++]=1; for(i=0;i<l2;i++)str[len++]=s2[i]; str[len]=0; da(str,len+1,300); calheight(str,len); for(i=1;i<=len;i++) height[i]=(height[i]>=k-1)?height[i]-k+1:0, f[i]=sa[i]<l1; height[len+1]=0; long long ans=0; for(int t=0;t<=1;t++) { long long top=0,ss=0; for(i=2;i<=len;i++) { if(f[i]!=t)ans+=ss; top++; a[top]=height[i+1]; b[top]=f[i]==t; ss+=(long long)a[top]*b[top]; while(top>=1&&a[top-1]>=a[top]) { ss-=(long long)(a[top-1]-a[top])*b[top-1]; a[top-1]=a[top]; b[top-1]+=b[top]; top--; } } } printf("%I64d\n",ans); } return 0; }