为防止广告，目前nocow只有登录用户能够创建新页面。如要创建页面请先登录/注册（新用户需要等待1个小时才能正常使用该功能）。
USACO/hidden
这篇文章可以证实是由NOCOW用户原创，不存在任何版权争议。 本文作者同意以GNU FDL、CC-by-sa和GNU LGPL（如果适用）三种版权发布此文章（不包括翻译文章中属于原始所有者的部分版权）。 如果你修改了这篇文章并且不同意用GNU FDL以外的版权发布，可以换一个版权模板或者移除此模板。
- 这是USACO Chapter 5 .5中的OI题目Hidden Passwords的介绍及题解，参见 翻译，C语言代码，C++语言代码，Pascal语言代码。
目录 |
[编辑] 问题分析
首先，为了解决环的情况，可以在这个字符串后面再接一个相同的字符串。这样不影响结果。 本题可以采用比较法。 我们可以用两个标记i、j表示两个待比较字符串（长度为n）的起始位置。初始时i=0，j=1。 每次比较以i开头和以j开头的字符串s[i]和s[j]的大小，如果s[i]>s[j]则i=j，否则j向后移k位，k表示s[i]和s[j]的最长相同前缀的长度，因为s[i]的前K位的字母都大于等于s[i]的第一个字母,而s[i]与s[j]的前K为字母相同,所以下一次只需比较s[i+k]与s[i]即可,k在比较大小时顺便可以求出。不停比较直到j≥n。 这种算法可以应付大多数数据，但是因为最坏情况下算法的时间复杂度是O(n^2)的，对于特殊构造的数据就不行了。不过USACO没有出这种数据，放心做吧。
几个需要注意的细节:
- 当比较时发现两个字符串相同时,直接输出0
- k的最小值应为1
//不应该吧，如果原字符串是abaaba按照你的方法输出是0而我认为正确的应该是2…只是发表一下个人意见而已：我认为如果s[i]>s[j]则i=j，j=j+1.不然就j=j+k。 By TtXu
//LS貌似是算错了吧，按照上面的方法运行出来就是2，参见pascal程序1。 From Error
- 本题为 最小表示法 问题.
（转自sevenlunar 和讯博客） 首先我们明确一个概念：最小后缀(least suffix)。
对于给定的一个串，将它的所有后缀按字典序排序，其中第一个后缀就是最小后缀。
那么如何求最小后缀呢？
最显然的方法是O(n2)的，这里我介绍一种O(n)的算法。
对于一个长度为n的主串s，设v[i]表示子串s[i..i+v[i]-1]，该子串的所有前缀在主串中所有相应长度的子串中字典序最小（这句比较绕，但是很关键一定要弄明白）。
比如对于串acab则v[3]=2，即子串'ab'的所有前缀('a','ab')中，'a'在所有长度为1的子串('a','c','b')中字典序最小，'ab'在所有长度为2的子串('ac','ca','ab')中字典序最小。
我们要求的是最大的v[i]，则i开始的主串的后缀就是最小后缀。
初始时v为0。设list记录当前所有的i，使得v[i]当前最大，初始时list=(1..n)。
对于每个在list中的i，
如果v[i+v[i]]>0，那么把s(i..i+v[i]-1)和s(i+v[i]..i+v[i]+v[i+v[i]]-1)合并后的s(i..i+v[i]+v[i+v[i]]-1)肯定最小，则v[i]=v[i]+v[i+v[i]]；
同时为了避免重复，把i+v[i]从list中去掉。
如果v[i+v[i]]=0，那么当且仅当s[i+v[i]]在所有s[j+v[j]]（j在list中）中最小时，v[i..i+v[i]]才最小，则v[i]=v[i]+1。
求出v后，把当前v最大的i放入list，其余的删掉，重复这个过程，直到list中只有1个i为止。
可以看出以上过程实际上就是不断地合并区间，而每个位置最多只访问一次，list中的位置最多删除一次，所以总的复杂度是O(n)的。
现在我们回到这道题上来，我们把主串复制两份，这样就解决了圈的问题。然后我们在串的最后加一个大于串中所有字符的字符（'z'+1）。
此时这个串的最小后缀所对应的开始位置i就是所求。
这是很显然的，因为最小后缀的前缀肯定是最小的。
ps.这道题Maigo的程序从编程复杂度上比这个简单多了，但是其实是可以设计出数据TLE的(39999个b+1个a)，只不过USACO和ZOJ都没有出这种数据。
ps.其实本题答案不应该仅仅原串复制后的最小后缀，因为题目中有要求出现位置最小，例如aaa应该输出0，但是按照上面那个方法求出的会是2
ps.对于上一个ps，复制以后增加一个比'z'还大的字符在串尾即可
又一个方法：
类似后缀数组，可在NlogN时间内求出子串任意长度的任意排名。
首先把字母复制一遍，处理后缀数组，得到2^k(k=0..log(n))的子串(后缀)的名次，然后：
字符串的长度N可以表示为二进制，位数不超过log(n),然后用类似后缀数组的倍增，把长度
N分成的块(每个块都是2^k),按照第一第二关键字，逐渐合并，每次合并用基数排序，O(N),
所以也是NLogN.
不过常数可能较大。
后缀数组是可行的，然而USACO又增加了数据（准确说改了题目），使得“aaaa”合法，那么使用完后缀数组后，我还用了kmp，不知神牛有无解决方法
（我觉得可以增加串尾符啊……{by Tearhap_断章})
我不明白LS的意思，我觉得用后缀数组做很水。。。。{by Morenan} Executing...
Test 1: TEST OK [0.011 secs, 2652 KB] Test 2: TEST OK [0.011 secs, 2652 KB] Test 3: TEST OK [0.011 secs, 2652 KB] Test 4: TEST OK [0.011 secs, 2652 KB] Test 5: TEST OK [0.011 secs, 2652 KB] Test 6: TEST OK [0.011 secs, 2652 KB] Test 7: TEST OK [0.032 secs, 2652 KB] Test 8: TEST OK [0.378 secs, 2652 KB] Test 9: TEST OK [0.367 secs, 2652 KB] Test 10: TEST OK [0.346 secs, 2652 KB] Test 11: TEST OK [0.248 secs, 2652 KB] Test 12: TEST OK [0.054 secs, 2652 KB] Test 13: TEST OK [0.011 secs, 2652 KB] Test 14: TEST OK [0.097 secs, 2652 KB]
微慢了点。
[编辑] 后缀数组
此题可以使用后缀数组，但需要做稍微改动。为了避免类似“aaaa”这样的数据带来的问题，我们可以在串的末尾加上无限个值为无限的字符。当然，没有必要真的加。只需要将下面两句话交换即可：
for(p=0,i=n-j+1;i<=n;++i) y[++p]=i; for(i=1;i<=n;++i) if(sa[i]>j) y[++p]=sa[i]-j;
↓
for(p=0,i=1;i<=n;++i) if(sa[i]>j) y[++p]=sa[i]-j; for(i=n-j+1;i<=n;++i) y[++p]=i;
Test 1: TEST OK [0.000 secs, 7364 KB] Test 2: TEST OK [0.000 secs, 7364 KB] Test 3: TEST OK [0.000 secs, 7364 KB] Test 4: TEST OK [0.000 secs, 7364 KB] Test 5: TEST OK [0.000 secs, 7364 KB] Test 6: TEST OK [0.000 secs, 7364 KB] Test 7: TEST OK [0.027 secs, 7364 KB] Test 8: TEST OK [0.270 secs, 7364 KB] Test 9: TEST OK [0.243 secs, 7364 KB] Test 10: TEST OK [0.243 secs, 7364 KB] Test 11: TEST OK [0.108 secs, 7364 KB] Test 12: TEST OK [0.000 secs, 7364 KB] Test 13: TEST OK [0.000 secs, 7364 KB] Test 14: TEST OK [0.027 secs, 7364 KB]
ps：
很明显的最小表示法吗……建议参考WC周源《最小表示思想的应用》,简洁易懂,程序还很快……
简单的代码实现请参考Pascal范例~
Executing...
Test 1: TEST OK [0.000 secs, 208 KB] Test 2: TEST OK [0.000 secs, 240 KB] Test 3: TEST OK [0.000 secs, 240 KB] Test 4: TEST OK [0.011 secs, 240 KB] Test 5: TEST OK [0.000 secs, 272 KB] Test 6: TEST OK [0.000 secs, 304 KB] Test 7: TEST OK [0.000 secs, 304 KB] Test 8: TEST OK [0.032 secs, 304 KB] Test 9: TEST OK [0.022 secs, 304 KB] Test 10: TEST OK [0.043 secs, 304 KB] Test 11: TEST OK [0.022 secs, 304 KB] Test 12: TEST OK [0.000 secs, 304 KB] Test 13: TEST OK [0.011 secs, 208 KB] Test 14: TEST OK [0.000 secs, 304 KB]
[编辑] 求助
请问最小表示法能保证正确性吗，有可能找出的是另一串相同的字符，而并非最小表示的啊.
(设指针i,j分别向后滑动k个位置后比较失败(k>=0)。假设s[i+k]≠s[j+k]：讨论 s[i+k] > s[j+k]：因为s[i+x]与s[j+x](0<=x<=k-1)对应相等，即有：s[i...i+k-1] = s[j...j+k-1]，现在已经在i+k位置处与j+k不相等且s[i+k]>s[j+k]，因此对指针i而言整个s[i]到s[k-1]都不是s的最小表示的起始位置，则PosMin(s)>i+k，所以i可以滑动到i+k+1仍可保证<=PosMin(s)。 反之对称地s[i+k]<s[j+k],j可以滑动到j+k+1仍可保证<=PosMin(s)。不管怎么样总有min(i,j) <= PosMin(s)，当k==len时，返回min(i,j)即为答案。因为i,j都是单调递增的，复杂度O(n)。)
[编辑] ORZ
硬是没看懂为什么是O(n)，但是我的时间很好的证明了：
USER: wang x [wx539181] TASK: hidden LANG: C++
Compiling... Compile: OK
Executing...
Test 1: TEST OK [0.000 secs, 3328 KB] Test 2: TEST OK [0.000 secs, 3328 KB] Test 3: TEST OK [0.000 secs, 3328 KB] Test 4: TEST OK [0.000 secs, 3328 KB] Test 5: TEST OK [0.000 secs, 3328 KB] Test 6: TEST OK [0.000 secs, 3328 KB] Test 7: TEST OK [0.000 secs, 3328 KB] Test 8: TEST OK [0.000 secs, 3328 KB] Test 9: TEST OK [0.000 secs, 3328 KB] Test 10: TEST OK [0.000 secs, 3328 KB] Test 11: TEST OK [0.000 secs, 3328 KB] Test 12: TEST OK [0.000 secs, 3328 KB] Test 13: TEST OK [0.000 secs, 3328 KB] Test 14: TEST OK [0.000 secs, 3328 KB]
All tests OK.详见C++ CODE
[编辑] 直接暴力就好了
可以在读入时统计每个字母第几次出现在哪个位置, 然后按字典序找到第一个出现次数非零的字母. 之后倒序记录每个位置上的该字母的连续出现次数Count[i], 并更新最大连续出现次数MAX, 特别注意此题是环状结构. 之后只处理Count[i] == MAX的位即可.
Executing...
Test 1: TEST OK [0.000 secs, 13964 KB] Test 2: TEST OK [0.027 secs, 13964 KB] Test 3: TEST OK [0.027 secs, 13964 KB] Test 4: TEST OK [0.027 secs, 13964 KB] Test 5: TEST OK [0.027 secs, 13964 KB] Test 6: TEST OK [0.027 secs, 13964 KB] Test 7: TEST OK [0.027 secs, 13964 KB] Test 8: TEST OK [0.027 secs, 14076 KB] Test 9: TEST OK [0.027 secs, 13964 KB] Test 10: TEST OK [0.027 secs, 13964 KB] Test 11: TEST OK [0.027 secs, 13964 KB] Test 12: TEST OK [0.027 secs, 13964 KB] Test 13: TEST OK [0.027 secs, 13964 KB] Test 14: TEST OK [0.918 secs, 13964 KB]
All tests OK.
最后一个点比较尴尬, 第11个点很明显是卡找A的..--Climber.pI
更猥琐的暴力—DY
Test 1: TEST OK [0.000 secs, 664 KB] Test 2: TEST OK [0.000 secs, 664 KB] Test 3: TEST OK [0.000 secs, 664 KB] Test 4: TEST OK [0.000 secs, 664 KB] Test 5: TEST OK [0.000 secs, 664 KB] Test 6: TEST OK [0.000 secs, 664 KB] Test 7: TEST OK [0.000 secs, 664 KB] Test 8: TEST OK [0.054 secs, 664 KB] Test 9: TEST OK [0.248 secs, 664 KB] Test 10: TEST OK [0.378 secs, 664 KB] Test 11: TEST OK [0.000 secs, 664 KB] Test 12: TEST OK [0.000 secs, 664 KB] Test 13: TEST OK [0.000 secs, 664 KB] Test 14: TEST OK [0.367 secs, 664 KB]
All tests OK.
只要扫描一遍，把最小的字母位置记录下来。而且连续的一串只需记第一个（想一想，为什么）。//冒充一下LRJ 然后枚举比较即可。
实在是没时间，只好写暴力，各位注意一下c++的string在暴力的时候很不好用，它那个[]操作符是有各种额外check的
要是想过，就得来个 const char* p = str.c_str();，然后把p当作c字符串来搞。 -- dp
红书模板P216..注意读入时候可能换行 ```
int pos = 0;
while (pos < N ) {
scanf("%s",str + pos);
pos = (int)strlen(str);
}
```
