欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

不相同的子串的个数

程序员文章站 2024-02-11 14:52:40
...

不相同的子串的个数

不相同的子串的个数

题目描述

 

给定一个字符串,求不相同的子串的个数。

 

 

输入

 

 输入数据第一行为一个数字T,表示数据组数。(T<=10)

接下来的T行,每行一个由小写或大写字母构成的字符串,字符串长度不超过50000。

 

输出

 

 对于每组数据,输出一行一个数字,表示答案。

 

样例输入

4
abbabba
dabddkababa
bacaba
baba

样例输出

17
55
17
7

提示

 

【题目来源】
spoj694,spoj705

sulotion

由于每个子串一定是某个后缀的前缀,相当于就是求后缀之间不相同前缀的个数.

加上(n-sa[i]+1)个新前缀,减掉height[i]个已经算过了。

#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<cmath>
#define maxn 500005
using namespace std;
int n,m,sa[maxn],rk[maxn],tp[maxn],tax[maxn],p;
int height[maxn],T;
char s[maxn];
long long ans;
void Qsort(){
    for(int i=0;i<=m;i++)tax[i]=0;
    for(int i=1;i<=n;i++)tax[rk[i]]++;
    for(int i=1;i<=m;i++)tax[i]+=tax[i-1];
    for(int i=n;i>=1;i--)sa[ tax[rk[tp[i]]]-- ]=tp[i];
}
void get_height(int n)
{
    int k=0,j;
    for(int i=1;i<=n;i++)
    {
        j=sa[rk[i]-1];
        if(k) k--;
        while(s[j+k]==s[i+k]) k++;
        height[rk[i]]=k;
    }
}
int main()
{
    cin>>T;
    while(T--){
    scanf("%s",s+1);
    n=strlen(s+1);
    for(int i=1;i<=n;i++)rk[i]=s[i]-'0',tp[i]=i;
    m=105;Qsort();
    for(int ws=1,p=0;p<n;m=p,ws<<=1){
        p=0;
        for(int i=1;i<=ws;i++)tp[++p]=n-ws+i;
        for(int i=1;i<=n;i++)if(sa[i]>ws)tp[++p]=sa[i]-ws;
        Qsort();
        swap(tp,rk);
        rk[sa[1]]=p=1;
        for(int i=2;i<=n;i++){
        rk[sa[i]]=(tp[sa[i-1]]==tp[sa[i]]&&tp[sa[i-1]+ws]==tp[sa[i]+ws])?p:++p;
        }
    }
    get_height(n);
        ans=0;
        for(int i=1;i<=n;i++)ans+=n+1-sa[i]-height[i];
        printf("%lld\n",ans);
    }
    return 0;
}

 

posted @ 2018-08-15 16:26 liankewei 阅读(...) 评论(...) 编辑 收藏