8.29 模拟题 T2 后缀数组
对应题目 : JZOJ 100037【NOIP2017提高A组模拟7.11】后缀数组
大概意思是说你之前获得了一个字符串，但是你现在忘了。现在你又想要知道这个字符串大小的最小值。但你现在只有那串字符串的后缀数组了，希望你能够由此求出答案。
数据有多组，n = 0 为结束标志。
Input
3
3 2 1
4
1 3 2 4
5
1 2 3 4 5
0
Output
1
3
2
那么我们要怎么做呢？其实这是一道考察我们后缀数组性质的题目。
关于后缀数组详解呢，可以参照这个：http://blog.csdn.net/yxuanwkeith/article/details/50636898
首先我们要知道关键的几个变量含义：
一是Rank，二是Sa，还有就是S。
S [ i ] 的意思是原数组中下标i ~ n 连续子串（即后缀）
Rank [ i ] 的意思是说S [ i ] 所有后缀中的排名。
Sa [ i ] 满足Suffix[SA[1]] < Suffix[SA[2]] …< Suffix[SA[Len]],即排名为i的后缀为Suffix[SA[i]] (与Rank是互逆运算)
然后我们观察题目，我们现在有了Sa这个数组，那么我们逆推，可以推出Rank数组对吧。
然后我们就可以使用rank[SA[i] + 1] >= rank[SA[i + 1] + 1] 这个厉害的东西。
这个东西有什么用呢？
我们可以由此推断S[SA[i]] < S[SA[i + 1]]
你看，这是不是就是我们想要的呢？
为什么呢？
我们想：
S [ 小 ]
S [ 大 ]
这样的两个东西，满足的必须条件是S [ 大 ] >= S [ 小 ] 对吧。
由于我们的要求是字符集尽量的要小，所以我们尽量去取等于的情况：
对于等于的情况呢，也就是说S [ 小 ] 以后的后缀应该要 <= S [ 大 ] 对吧。
而对应的我们观察那个厉害的东西是不是就是这么回事呢？
我们转换一下就可以发现这是等价的，所以，
对就是这么回事！
满足一个，我们就应该在 ans 上 ++，最后直接输出就好了。
还是附上一个简短的代码吧：
#include<iostream> #include<cstring> #include<cstdio> #include<algorithm> #define N 100010 using namespace std; int n; int Sa[N],Rank[N]; int main() { // freopen("sa.in","r",stdin); // freopen("sa.out","w",stdout); while(~scanf("%d",&n) && n != 0) { for(int i = 1; i <= n; i++) scanf("%d",&Sa[i]); for(int i = 1; i <= n; i++) Rank[Sa[i]] = i; Rank[n+1] = 0; int ans = 1; for(int i = 1; i < n; i++) { if(Rank[Sa[i] + 1] >= Rank[Sa[i+1] + 1]) ans ++; } printf("%d ",ans); } return 0; }