POJ 3415 求两个字符串间长度不小于k的公共子串的个数

Common Substrings
Time Limit: 5000MS   Memory Limit: 65536K
Total Submissions: 6409   Accepted: 2117

Description

A substring of a string T is defined as:

T(i, k)=TiTi+1...Ti+k-1, 1≤ii+k-1≤|T|.

Given two strings A, B and one integer K, we defineS, a set of triples (i, j, k):

S = {(i, j, k) | kK,A(i, k)=B(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 ≤ Kmin{|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;
}


POJ 3415 求两个字符串间长度不小于k的公共子串的个数

上一篇:protocol协议


下一篇:如何彻底删除QQ程序