JZOJ 100037.后缀数组

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

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

转移的话,首先考虑能不能和上一个选一样的,即如果后缀 SAi1+1SA_{i - 1} + 1 比后缀 SAi+1SA_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]);
}
}