poj3415

题目

Common Substrings
Time Limit: 5000MS Memory Limit: 65536K
Total Submissions: 10932 Accepted: 3622
Description

A substring of a string T is defined as:

T(i, k)=TiTi+1…Ti+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| ≤ 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

题解

简化问题，发现是问从i,j两个位置开始的长度大于等于k的公共字符串的个数和，那么考虑用后缀数组做
但是如果在处理出height之后直接做的话时间复杂度是n^2的，所以考虑用一个单调栈优化
st1,st2是两个单调栈，存储的是与当前字符串的公共前缀的长度，cc1,cc2表示对应的个数
那么我们在给排序后的后缀一次求值的时候顺便维护一下这两个单调栈的信息，就可以快速的求值了
这题其实比较好想，但是发现之前学sa时候的模板有一个问题,x,y数组范围应该开到字符串的两倍才对啊。。。

贴代码

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<cstring>
#define fo(i,a,b) for(i=a;i<=b;i++)
#define ll long long
using namespace std;

const int ma1=200005,maxn=100005;

int sa[ma1],rank[ma1],height[ma1],x[ma1*2],y[ma1*2],buc[ma1],st1[ma1],st2[ma1],cc1[ma1],cc2[ma1];
char s1[maxn],s[ma1];
int i,j,k,l,n,m,len,len1,len2,p,t1,t2;
int now1,now2,top1,top2;
ll ans,zong1,zong2;
void gesa(){
    m=96+26;
    memset(x,0,sizeof(x));
    fo(i,0,len-1) x[i]=s[i];
    fo(i,1,m) buc[i]=0;
    fo(i,0,len-1) buc[x[i]]++;
    fo(i,1,m) buc[i]+=buc[i-1];
    fo(i,0,len-1) sa[buc[x[i]]--]=i;
    for(k=1;k<len;k=k*2){
        p=0;
        fo(i,len-k,len-1) y[++p]=i;
        fo(i,1,len) if (sa[i]>=k) y[++p]=sa[i]-k;
        fo(i,1,m) buc[i]=0;
        fo(i,0,len-1) buc[x[i]]++;
        fo(i,1,m) buc[i]+=buc[i-1];
        for(i=len;i>=1;i--) sa[buc[x[y[i]]]--]=y[i];
        fo(i,0,len*2) y[i]=x[i];
        x[sa[1]]=1;
        fo(i,2,len){
            if (y[sa[i]]==y[sa[i-1]] && y[sa[i]+k]==y[sa[i-1]+k]) x[sa[i]]=x[sa[i-1]]; else
            x[sa[i]]=x[sa[i-1]]+1;
        }
        m=x[sa[len]];
        if (m==len) break;
    }
    fo(i,1,len) rank[sa[i]]=i;
}

void gehei(){
    k=0;
    fo(i,0,len-1){
        if (rank[i]==1){
            height[rank[i]]=0;
            continue;
        }
        if (k) k--;
        t1=i+k; t2=sa[rank[i]-1]+k;
        while (t1<len && t2<len){
            if (s[t1]=='#' || s[t2]=='#') break;
            if (s[t1]==s[t2]) k++; else break;
            t1++; t2++;
        }
        height[rank[i]]=k;
        if (s[i]=='#') height[i]=0;
    }
}
void geans(){
    ans=0;
    memset(cc1,0,sizeof(cc1));
    memset(cc2,0,sizeof(cc2));
    zong1=zong2=0;
    top1=top2=1;
    int x;
    k=n;
    fo(i,1,len)
    if (s[sa[i]]!='#')
    {
        x=height[i]-k+1;
        while (top2>1 && st2[top2-1]>=x) {
            zong2-=(st2[top2]-st2[top2-1])*cc2[top2];
            cc2[top2-1]+=cc2[top2]; cc2[top2--]=0;
        }

        if (st2[top2]>x && x>0){
            zong2-=(st2[top2]-x)*(cc2[top2]);
            st2[top2]=x;
        }
        while (top1>1 && st1[top1-1]>=x){
            zong1-=(st1[top1]-st1[top1-1])*cc1[top1];
            cc1[top1-1]+=cc1[top1]; cc1[top1--]=0;
        }
        if (st1[top1]>x && x>0){
            zong1-=(st1[top1]-x)*(cc1[top1]);
            st1[top1]=x;
        }
        if (x<=0) continue;
        if (sa[i-1]<len1){
            if (st1[top1]<x) st1[++top1]=x;
            cc1[top1]+=1;
            zong1+=x;
        } else{
            if (st2[top2]<x) st2[++top2]=x;
            cc2[top2]+=1;
            zong2+=x;
        }
        if (sa[i]<len1) ans+=zong2; else ans+=zong1;
    }
    printf("%lld\n",ans);
}
int main(){
    freopen("3415.in","r",stdin);
    freopen("3415.out","w",stdout);
    n=1;
    while (n){
        scanf("%d",&n);
        if (!n) break;
        scanf("%s",&s1);
        len1=strlen(s1);
        fo(i,0,len1-1) s[i]=s1[i];
        scanf("%s",&s1);
        len2=strlen(s1);
        s[len1]='#';
        fo(i,len1+1,len1+len2) s[i]=s1[i-len1-1];
        len=len1+len2+1;
        gesa();
        gehei();
        geans();
    }
    return 0;
}