USACO Hidden Password

对于循环，通用的方法是把字符串复制一遍接在原串的后面，比如：
abcde --> abcdeabcde

题目要求输出排序最小的字符串的首字母所在位置，可以想到一个朴素的办法。
用minp记录答案，初始化为0，然后
for(i = 1;i < L;i ++)
   if(strncmp(str + i, str + minp, L) < 0)
      minp = i;
容易知道，这是一个O(n^2)的算法，当测试数据是100000个a时，就会超时。

最后不得已上NOCOW看了别人的题解，找到了一个比较简便的方法，可以通过所有测试数据，不过正确性有待证明。这个算法主要建立在安徽周源的论文《浅析“最小表示法”思想在字符串循环同构问题中的应用》上，读者还可以参考HDU-2609.

代码如下

C语言: 高亮代码由发芽网提供

01 #include
02 #include
03 #include
04
05 long l;
06 char str[200003];
07
08 void init()
09 {
10    long i;
11    char c;
12    scanf("%ld\n",&l);
13    for(i = 0;i < l;)
14    {
15        c = getchar();
16        if(c <= 'z' && c >= 'a')
17            str[i ++] = c;
18    }
19    strncpy(str + l,str,l);    //转环为链
20 }
21
22 int main()
23 {
24    freopen("hidden.in","r",stdin);
25    freopen("hidden.out","w",stdout);
26    init();
27    long i,j,k,minp;
28    for(i = 0,j = 1,k = 0;i < l && j < l;)    //请参考周源的论文
29    {
30        if(k == l)    break;
31        if(*(str + i + k) == *(str + j + k))
32            {k ++;continue;}
33        if(*(str + i + k) > *(str + j + k))
34        {
35            i += k + 1;
36            k = 0;
37        }
38        else
39        {
40            j += k + 1;
41            k = 0;
42        }
43        if(i == j)    j ++;  //避免i,j相等，发生误判
44    }
45    minp = (i < j)?i:j;
46    printf("%ld\n",minp);
47    return 0;
48 }

为什么说这种算法正确性有待证明？

因为HDU-2609和那篇论文都是正向使用这个算法的，即用最小表示法判断两个环是否相同。

而上面的代码却逆用这个方法：已知两个相同的环，求它们在哪两个位置开始相同。 

==================================================

USACO上面的Analysis介绍了一种不错的DP算法，不过它给出的代码可读性太差了。于是我参考了这一篇博文（链接）。先使用同样的方法处理环。然后定义数组len[],len[i] = k表示以i开头的k个字符组成的串，与其他位置连续k个字符组成的串相比，是最小的。
那么，容易知道，两个相邻的最小串相连依然是最小的，并且长度增加。于是就有了下面的转移方程：

len[i] += len[i + len[i]]   当 len[i + len[i]] > 0
len[i] += 1                      当 s[len[i]]是最小的字符

需要注意的是，当这两个串相连后，前一个串长度是两者之和，所以下次计算的时候就没有必要再算后一个串了，因此可以把它从链表中除去（在下面的代码中使用数组模拟双向链表）。

C语言: 高亮代码由发芽网提供

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAXN 200010

long len[MAXN];
long prev[MAXN],next[MAXN];  //Two-way linking list
long head;
char str[MAXN];
long l,nl;

void init()
{
   scanf("%ld\n",&l);
   long i;
   for(i = 0;i < MAXN;i ++)   //初始化为最大值，方便dp
       str[i] = 'z' + 1;
   for(i = 0;i < l;)
   {
       scanf("%c",str + i);
       str[i + l] = str[i];
       if(str[i] <= 'z' && str[i] >= 'a')    i ++;
   }
   nl = l * 2 + 1;
}

void dp_init()
{
   memset(len,0,sizeof(len));
   long i;
   for(i = 0;i < nl;i ++)   //初始化双向链表
   {
       prev[i] = i - 1;
       next[i] = i + 1;
   }
   next[nl - 1] = -1;
   prev[0] = -1;
   head = 0;
}

void del(long p)    //remove node p from list
{
   if(head == p)    head = next[p];
   if(next[p] != -1)    prev[next[p]] = prev[p];
   if(prev[p] != -1)    next[prev[p]] = next[p];
}

void dp()
{
   long max,i,prevmax;
   int minchar;
   prevmax = -1;
   while(1)
   {
       minchar = 10000;
       for(i = head;i != -1;i = next[i])
           if(str[i + len[i]] < minchar)        minchar = str[i + len[i]];
       max = -1;
       for(i = head;i != -1;i = next[i])
       {
           if(i + len[i] > nl)    continue;
           if(len[i + len[i]] > 0)
           {
               del(i + len[i]);
               len[i] += len[i + len[i]];
           }
           else if(len[i + len[i]] == 0 && str[i + len[i]] == minchar)
               len[i] ++;
           if(len[i] > max)
               max = len[i];
       }
       for(i = head;i != -1;i = next[i])
           if(len[i] < max)    del(i);
       if(max == l)    break;    //max最大只可能是字符串长度
       if(max == prevmax)    //当max不再变更时跳出
           break;
       else    prevmax = max;
   }
   printf("%ld\n",head);
}

int main()
{
   freopen("hidden.in","r",stdin);
   freopen("hidden.out","w",stdout);
   init();
   dp_init();
   dp();
   return 0;
}