JZOJ 100037 后缀数组

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

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

转移的话，首先考虑能不能和上一个选一样的，即如果后缀 SAi−1+1 比后缀 SAi+1 小，就可以选一样的。
否则，会发现不满足条件。

代码：

#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]);
    }
}