题意很简单,找两个串长度大于等于k的公共子串数;
需要用单调队列来优化,用两次分别统计 A串与在A前面的B串的公共子串数 和 B串与在B前面的A串的公共子串数
过程大概是每入栈一个元素结果都加上一个tot,然后就是维护这个tot。。。
如果入栈的元素比栈顶的大,那tot就加上h [ i ] - k + 1,否则,就要维护栈单调递增的性质,把前面比它height值大的元素去掉,tot也相应的减少 num[ top ] * ( st [ top] - h [ i ] )个。比如栈中原来是 2,3,4 再加一个2,那么前面4个数的公共长度就变成2了,所以要tot要减小一点。。。减小之后的2的权重就会增加,比如在加入2之后,栈中只有一个元素2了。这时再加入一个1。1会把2踢掉,但是这个2表示了2,3,4,2这几个后缀,2的权重会变大。所以栈顶元素num [top ]也需要更新
Common Substrings
Description A substring of a string T is defined as: Given two strings A, B and one integer K, we define S, a set of triples (i, 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 Output For each case, output an integer |S|. Sample Input 2 aababaa abaabaa 1 xx xx 0 Sample Output 22 5 Source
POJ Monthly--2007.10.06, wintokk
|
[Submit] [Go Back] [Status] [Discuss]
#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> using namespace std; typedef long long int LL; const int maxn=200200; int sa[maxn],rank[maxn],rank2[maxn],h[maxn],c[maxn],*x,*y,ans[maxn]; char str[maxn]; bool cmp(int* r,int a,int b,int l,int n) { if(r[a]==r[b]&&a+l<n&&b+l<n&&r[a+l]==r[b+l]) return true; return false; } void radix_sort(int n,int sz) { for(int i=0;i<sz;i++) c[i]=0; for(int i=0;i<n;i++) c[x[y[i]]]++; for(int i=1;i<sz;i++) c[i]+=c[i-1]; for(int i=n-1;i>=0;i--) sa[--c[x[y[i]]]]=y[i]; } void get_sa(char c[],int n,int sz=128) { x=rank,y=rank2; for(int i=0;i<n;i++) x[i]=c[i],y[i]=i; radix_sort(n,sz); for(int len=1;len<n;len<<=1) { int yid=0; for(int i=n-len;i<n;i++) y[yid++]=i; for(int i=0;i<n;i++) if(sa[i]>=len) y[yid++]=sa[i]-len; radix_sort(n,sz); swap(x,y); x[sa[0]]=yid=0; for(int i=1;i<n;i++) { x[sa[i]]=cmp(y,sa[i],sa[i-1],len,n)?yid:++yid; } sz=yid+1; if(sz>=n) break; } for(int i=0;i<n;i++) rank[i]=x[i]; } void get_h(char str[],int n) { int k=0;h[0]=0; for(int i=0;i<n;i++) { if(rank[i]==0) continue; k=max(k-1,0); int j=sa[rank[i]-1]; while(i+k<n&&j+k<n&&str[i+k]==str[j+k]) k++; h[rank[i]]=k; } } int kaka,len1,len; LL num[maxn],st[maxn]; int main() { while(scanf("%d",&kaka)!=EOF&&kaka) { scanf("%s",str); len1=strlen(str); str[len1]=127; scanf("%s",str+len1+1); len=strlen(str); get_sa(str,len); get_h(str,len); LL ans=0,tot=0,top=0,tp=0; memset(num,0,sizeof(num)); memset(st,0,sizeof(st)); for(int i=1;i<len;i++) { if(h[i]<kaka) { tot=top=0; } else { tp=0; if(sa[i-1]>len1) { tp=1; tot+=h[i]-kaka+1; } while(top&&h[i]<=st[top]) { tot-=num[top]*(st[top]-h[i]); tp+=num[top]; top--; } if(sa[i]<len1) ans+=tot; top++; st[top]=h[i]; num[top]=tp; } } tot=top=0; for(int i=1;i<len;i++) { if(h[i]<kaka) { tot=top=0; } else { tp=0; if(sa[i-1]<len1) { tp=1; tot+=h[i]-kaka+1; } while(top&&h[i]<=st[top]) { tot-=num[top]*(st[top]-h[i]); tp+=num[top]; top--; } if(sa[i]>len1) ans+=tot; top++; st[top]=h[i]; num[top]=tp; } } printf("%I64d\n",ans); } return 0; }