题解 P1709 【[USACO5.5]隐藏口令Hidden Password】

· · 题解

我们以题目中的数据为例，有如下的一个字符串：

对于这个字符串，我们定义两个指针分别为 i 和 j 分别指向 ‘a’ 和 ’n’ 即 i = 0 j = 1 再定义一个累加器 k 则表示分别以 i 和 j 为首的字符串的第 k 个字符.

根据贪心思想,每一项显然要选最小的最好。在这里 ’n’ 的字典序大于 ’a’ 那么j显然不会是我们所要的答案那么我们就对j进行移位即 j++接下来我们便重复上面的操作

因为 i 和 j 所指的值是相同的，所以我们并不能通过比较这一位从而得出这两个字符串的顺序关系所以我们就要对 k 进行移位即 k++

我们对 i+k 和 j+k 所指的字符进行比较，显然可以得出 ’b’ 是比 ’n’ 要更优的那么这时候我们就要对i进行移位，因为在 [i ,i+k) 内我们都已经判断完了，那么我们就可以将 i 移到 i+k+1 继续接下来的判断。根据如上的操作我们就可以写出如下的伪代码:

    i = 0 ; j = 1 ; k = 0;
    while(i < length && j < length){
        if s[i + k] == s[j + k] k++
        if s[i + k] >  s[j + k] i = i + k + 1;
        if s[i + k] <  s[j + k] j = j + k + 1;
        ……
    }

但是我们还要考虑以下几个问题

1.当i=j时，我们的操作便无法正常的运行，因为显然的在i=j时，i+k=j+k，这样的话我们的k就会不断的增加从而导致WA

  1. i+k 和 j+k是可能越界的

  2. k是可能大于length的

解决方法如下:

1.当i=j时，j++

2.只要将i+k和j+k Mod length即可

3.限制k < length ,在k = length 直接返回i和j中位置较前的即可

完整代码如下:

#include <bits/stdc++.h>
using namespace std;
const int maxn=5000110;
int n;
char s[maxn];
int Mini(int l)    
{    
    int i,j,k;  
    i=0;j=1;k=0;  
    while(i<l&&j<l)  
    {  
        k=0;  
        while(s[(i+k)%l]==s[(j+k)%l]&&k<l) k++;  
        if(k==l) return (i<j)?i:j;  
        if(s[(i+k)%l]>s[(j+k)%l])i=i+k+1;
        else j=j+k+1;
        if(i==j)j++;
    } 
    return (i<j)?i:j;
}     
int main()
{
    cin>>n;
    for(int i=0;i<n;i++)cin>>s[i];
    int l=Mini(n);
    cout<<l<<endl;
    return 0;
}