程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> POJ3415:Common Substrings(後綴數組+單調棧)

POJ3415:Common Substrings(後綴數組+單調棧)

編輯：C++入門知識

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; iheight[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;
}