专题八 字符串

题解字符串

[题目][A]

最小表示法

题目大意：

有N个测试样例，每个测试有一个字符串，输出这个字符串循环同构的最小表示的开始下标i。(i要求尽量取小，当有多个最小表示的时候)

解题思路：

用i,j来记录较小字典序的字符串的开始位置。初始化i=0,j=1，然后比较s[i+k],s[j+k]的大小，如果相等，就继续比较下一个字符，否则将大的字符的初始下标往后移动k+1位（前一次两个字符串匹配的长度+1），如果两个下标位置i,j相等，则将j加一，错开。最后当i或者j大于了字符串长度，即所有情况都处理完了。这时，输出较小的下标。

AC代码：

#include <cstdio>
#include <iostream>
#include <cstring>
#include <cstdlib>
using namespace std;
char a[10005];
int getmin(int l)
{
    int i = 0,j = 1,k = 0,t;
    while(i < l && j < l)
    {
        if(k == l) return i;
        t = a[(i+k)%l] - a[(j+k)%l];
        if(t == 0) k++;
        else
        {
            if(t > 0) i += k+1;
            else j += k+1;
            if(i == j) j++;
            k = 0;
        }
    }
    if(i < l) return i;
    else return j;
}
int main()
{
   // freopen("in.txt","r",stdin);
    int n;
    scanf("%d",&n);
    while(n--)
    {
        scanf("%s",a);
        printf("%d\n",getmin(strlen(a)) + 1);
    }
    return 0;
}