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
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
题目大意:
给定两串A，B，找出A，B的长度大于k的公共子串的个数
题解：
显然后缀数组，将两个串合并 然后显然中间加一个‘#’阻断height越界
然后会发现求出high之后两串若分属A，B两串 显然 对答案贡献为lcp-k+1
再根据老套路 利用 height 递增的性质去维护单调栈，记录栈中lcp-k+1的值的总和 tot
如果当前height[i]大于栈顶就统计
如果height[i]<=栈顶 我们直接将栈顶和height[i]合并
调了很久最后发现把l开成了char = =|
1 #include <algorithm> 2 #include <iostream> 3 #include <cstdlib> 4 #include <cstring> 5 #include <cstdio> 6 #include <cmath> 7 using namespace std; 8 typedef long long ll; 9 const int N=400005; 10 int s[N];char S1[N],S2[N];int n,l,tmp[N],rk[N],sa[N],high[N],K,k; 11 bool comp(int i,int j){ 12 if(rk[i]!=rk[j])return rk[i]<rk[j]; 13 int ri=i+k<=n?rk[i+k]:-1; 14 int rj=j+k<=n?rk[j+k]:-1; 15 return ri<rj; 16 } 17 void Getsa(){ 18 for(int i=1;i<=n;i++){ 19 sa[i]=i;rk[i]=s[i]; 20 } 21 for(k=1;k<=n;k<<=1){ 22 sort(sa+1,sa+n+1,comp); 23 for(int i=1;i<=n;i++)tmp[sa[i]]=tmp[sa[i-1]]+comp(sa[i-1],sa[i]); 24 for(int i=1;i<=n;i++)rk[i]=tmp[i]; 25 } 26 } 27 void Gethight(){ 28 int h=0,j; 29 for(int i=1;i<=n;i++){ 30 j=sa[rk[i]-1]; 31 if(h)h--; 32 for(;i+h<=n && j+h<=n;h++)if(s[i+h]!=s[j+h])break; 33 high[rk[i]-1]=h; 34 } 35 } 36 ll ans=0; 37 struct stacker{ 38 int lcp,cnt; 39 }st[N<<1]; 40 void Getanswer() 41 { 42 ll tot=0,cnt=0;int top=0; 43 for(int i=1;i<n;i++){ 44 if(high[i]<K){ 45 top=tot=0; 46 continue; 47 } 48 cnt=0; 49 if(sa[i]<l)cnt++,tot+=high[i]-K+1; 50 while(top && high[i]<=st[top].lcp){ 51 tot-=(ll)(st[top].lcp-high[i])*st[top].cnt; 52 cnt+=st[top].cnt; 53 top--; 54 } 55 st[++top].lcp=high[i];st[top].cnt=cnt; 56 if(sa[i+1]>l)ans+=tot; 57 } 58 tot=0;top=0;cnt=0; 59 for(int i=1;i<n;i++){ 60 if(high[i]<K){ 61 top=tot=0; 62 continue; 63 } 64 cnt=0; 65 if(sa[i]>l)cnt++,tot+=high[i]-K+1; 66 while(top && high[i]<=st[top].lcp){ 67 tot-=(ll)(st[top].lcp-high[i])*st[top].cnt; 68 cnt+=st[top].cnt; 69 top--; 70 } 71 st[++top].lcp=high[i];st[top].cnt=cnt; 72 if(sa[i+1]<l)ans+=tot; 73 } 74 } 75 void work(){ 76 n=0;ans=0; 77 scanf("%s%s",S1,S2); 78 l=strlen(S1); 79 for(int i=0;i<l;i++)s[++n]=S1[i]; 80 s[++n]='#';l++; 81 for(int i=0,sz=strlen(S2);i<sz;i++)s[++n]=S2[i]; 82 s[n+1]=0; 83 Getsa(); 84 Gethight(); 85 Getanswer(); 86 printf("%lld ",ans); 87 } 88 int main() 89 { 90 freopen("pp.in","r",stdin); 91 freopen("pp.out","w",stdout); 92 while(scanf("%d",&K)) 93 { 94 if(!K)break; 95 work(); 96 } 97 return 0; 98 }