POJ3415:Common Substrings(后缀数组+单调栈) - c++编程基础

TOP

POJ3415:Common Substrings(后缀数组+单调栈)

2015-11-21 00:59:52 来源: 作者: 【大中小】浏览:1次

Tags：POJ3415:Common Substrings 后缀单调

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

#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #include 
      
        #include
        #include 
        
          #include 
         
           #include 
          
            #include 
           
             #include 
            
              #include 
             
               using namespace std; #define LS 2*i #define RS 2*i+1 #define UP(i,x,y) for(i=x;i<=y;i++) #define DOWN(i,x,y) for(i=x;i>=y;i--) #define MEM(a,x) memset(a,x,sizeof(a)) #define W(a) while(a) #define gcd(a,b) __gcd(a,b) #define LL long long #define N (2*100000+10) #define MOD 1000000007 #define INF 0x3f3f3f3f #define EXP 1e-8 int wa[N],wb[N],wm[N],wv[N],sa[N]; int *rank,height[N],s[N],a[N]; //sa:字典序中排第i位的起始位置在str中第sa[i] //rank:就是str第i个位置的后缀是在字典序排第几 //height：字典序排i和i-1的后缀的最长公共前缀 bool cmp(int *r,int a,int b,int l) { return r[a] == r[b] && r[a+l] == r[b+l]; } void getsa(int *r,int *sa,int n,int m) { int *x=wa,*y=wb,*t; for(int i=0; i
              
               =0; --i)sa[--wm[x[i]]]=i; for(int i=0,j=1,p=0; p
               
                =j)y[p++]=sa[i]-j; for(i=0; i
                
                 =0; --i)sa[--wm[x[y[i]]]]=y[i]; for(t=x,x=y,y=t,i=p=1,x[sa[0]]=0; i
                 
                  height[i]-k+1; size--) { num[mark[size]] += height[i]-k+1-sta[size]; sta[size] = height[i]-k+1; } sta[++top] = height[i]-k+1; if(sa[i-1]
                  
                   len) mark[top] = 2; num[mark[top]]+=height[i]-k+1; if(sa[i]
                   
                    len) sum+=num[1]; } } return sum; } int main() { int i,j; while(~scanf("%d",&k),k) { scanf("%s",s1); int n = 0; for(n = 0;s1[n]!='\0';n++) s[n] = s1[n]; s[len1=n] = '#'; scanf("%s",s1+n+1); n++; for(;s1[n]!='\0';n++) s[n] = s1[n]; s[n] = 0; getsa(s,sa,n+1,201); getheight(s,sa,n); printf("%lld\n",solve(n,len1,k)); } return 0; }


【大中小】【打印】【繁体】【投稿】【收藏】【推荐】【举报】【评论】【关闭】【返回顶部】
分享到:
上一篇：LightOJ1013---Love Calculator (..	下一篇：友元(友元函数、友元类和友元成员..

帐　　号:

密码: (新用户注册)

验证码:

表　　情:

内　　容: