POJ 3415 Common Substrings - c++编程基础

题意很简单，找两个串长度大于等于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

Time Limit: 5000MS		Memory Limit: 65536K
Total Submissions: 6390		Accepted: 2104

Description

A substring of a string T is defined as:

T( i, k)= T_iT_i ₊₁... T_i+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| ≤ 10⁵
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

Source

POJ Monthly--2007.10.06, wintokk

[Submit] [Go Back] [Status] [Discuss]

#include 
  
   
#include 
   
     #include 
    
      #include 
     
       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
      
       =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
       
        =len) y[yid++]=sa[i]-len; radix_sort(n,sz); swap(x,y); x[sa[0]]=yid=0; for(int i=1;i
        
         =n) break; } for(int i=0;i
         
          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; }