JZOJ 100037 后缀数组

发表于 | 分类于 |

这题和上次写的那题其实套路是一样的，无聊刷水题的时候发现的。

同样，按照后缀数组来转移，以便处理字典序相关的一些因素。
设 \(f_i\) 表示要满足后缀数组的前 \(i\) 位，字符集的大小至少是多少。

转移的话，首先考虑能不能和上一个选一样的，即如果后缀 \(SA_{i - 1} + 1\) 比后缀 \(SA_i + 1\) 小，就可以选一样的。
否则，会发现不满足条件。

代码： 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <cstdio>
using namespace std;
const int N = 1e5;
int n;
int sa[N + 5],rk[N + 5];
int f[N + 5];
int main()
{
    while(~scanf("%d",&n) && n)
    {
        for(register int i = 1;i <= n;++i)
            scanf("%d",sa + i),rk[sa[i]] = i;
        f[1] = 1;
        for(register int i = 1;i < n;++i)
            if(rk[sa[i] + 1] > rk[sa[i + 1] + 1])
                f[i + 1] = f[i] + 1;
            else
                f[i + 1] = f[i];
        printf("%d\n",f[n]);
    }
}