【洛谷P2408】不同子串个数 以及此类问题的拓展

发表于 | 更新于 | 分类于 ， | 评论数： | 阅读次数：
用4道题来讲解这种类型的题目。

题目背景

因为NOI被虐傻了，蒟蒻的YJQ准备来学习一下字符串，于是它碰到了这样一道题：

题目描述

给你一个长为$N$的字符串，求不同的子串的个数。

我们定义两个子串不同，当且仅当有这两个子串长度不一样 或者长度一样且有任意一位不一样。

子串的定义：原字符串中连续的一段字符组成的字符串。

输入输出格式

输入格式：

第一行一个整数$N$。

接下来一行$N$个字符表示给出的字符串。

输出格式：

一行一个整数，表示不一样的子串个数。

1

题解：

知识点：

后缀数组，LCP

分析：

其实求本质不同的子串的个数这类问题，很容易联想到后缀数据结构。其实可以发现子串不同相当于所有后缀的前缀不同的情况，所以我们把问题的统计变成了统计前缀的不同个数。

我们以$sa[1],sa[2],sa[3],sa[i] \cdots，sa[n]$的顺序统计每个$suffix$,可以发现每次加入的后缀的前缀的个数为$n-sa[i]+1$,但是这里面有很多是重复的，我们要把它们减掉，又$height[i]$的定义我们可以知道，既然前$i-1$处已经计算过$suffix(sa[i])的前height[i]$位了，那么我们把$height[i]$减掉就是答案了，这样就可以线性地解决问题。

时间复杂度：$O(n\log_{2}n)$

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;

const int maxn=100010;
int n,m=128,sa[maxn],rnk[maxn],y[maxn],height[maxn],c[maxn];
char s[maxn];
long long ans;//答案会很大，要开够

void sort()
{
    int i;
    memset(c,0,sizeof(c));
    for (i=1;i<=n;i++)
        c[rnk[i]]++;
    for (i=2;i<=m;i++)
        c[i]+=c[i-1];
    for (i=n;i>=1;i--)
        sa[c[rnk[y[i]]]--]=y[i];
}

void getsa()
{
    int i,p=0,k;
    for (i=1;i<=n;i++)
    {
        rnk[i]=s[i];
        y[i]=i;
    }
    sort();
    for (k=1;p<n;k<<=1,m=p)
    {
        p=0;
        for (i=n-k+1;i<=n;i++)
            y[++p]=i;
        for (i=1;i<=n;i++)
            if (sa[i]>k)
                y[++p]=sa[i]-k;
        sort();
        swap(rnk,y);
        rnk[sa[1]]=p=1;
        for (i=2;i<=n;i++)
            rnk[sa[i]]=(y[sa[i]]==y[sa[i-1]]&&y[sa[i]+k]==y[sa[i-1]+k])?p:++p;
    }
}

void getheight()
{
    int i,j,k=0;
    for (i=1;i<=n;i++)
    {
        if (k)
            k--;
        j=sa[rnk[i]-1];
        while (s[j+k]==s[i+k])
            k++;
        height[rnk[i]]=k;
    }
}

int main()
{
    int i;
    scanf("%d%s",&n,s+1);
    getsa();
    getheight();
    for (i=1;i<=n;i++)
        ans+=n-sa[i]+1-height[i];
    printf("%lld\n",ans);
    return 0;
}

现在我们考虑变成多组数据，在时间复杂度允许的情况下，直接搞就好了，但是注意字符集大小每次要恢复到128，数组要清空。(Eg.SPOJ694 705)

而LZOJ里面的那道把数据组数开到了$10^{3}$，但是同时字符集变小了，这样也是可以跑过去的（常数不能太大）。

显示 Gitment 评论