ZOJ 1729 Hidden Password（最小表示法模板题）

骑猪看日落 2022-06-09 01:22 130阅读 0赞

Some time the programmers have very strange ways to hide their passwords. See for example how Billy "Hacker" Geits hide his password. Billy chooses a string S composed of small Latin letters with length L. Then he makes all L-1 one-letter left cyclic shifts of the string and takes as a password one prefix of the lexicographically first of the obtained strings (including S). For example let consider the string alabala. The cyclic one-letter left shifts (including the initial string) are:

alabala  
labalaa  
abalaal  
balaala  
alaalab  
laalaba  
aalabal

and lexicographically first of them is the string aalabal. The first letter of this string is in position 6 in the initial string (the positions in the string are counted from 0).

Write a program that for given string S finds the start position of the smallest lexicographically one-letter left cyclic shift of this string. If the smallest lexicographically left shift appears more than once then the program have to output the smallest initial position.

Your program has to be ready to solve more than one test case. The first line of the input file will contains only the number T of the test cases. Each of the following T lines will describe one test case - first the length L of the string (5 <= L <= 100000) and then, separated by one space, the string S itself.

The output file have to contain exactly T lines with a single number each - the initial position found by your program.

**Sample Input**

2  
6 baabaa  
7 alabala

**Sample Output**

1  
6

思路：

完全就是一道最小表示法的裸题。。如果不明白最小表示法的可以学一下：

先解这一题要知道什么是最大最小表示法

这个要举个例子，比如一个字符串abcde

那么求该串的同构串中字典序最小的那个就是最小表示法，是一个串的一种性质，同构串就是每次将串整体循环移动一位形成的新串

比如刚刚那个串的同构串有bcdea，cdeab，deabc，eabcd,求其中最小的那个串就是最小表示法

代码：

#include<iostream>
    #include<cstring>
    #include<stdio.h>
    #include<math.h>
    #include<string>
    #include<stdio.h>
    #include<queue>
    #include<stack>
    #include<map>
    #include<vector>
    #include<deque>
    using namespace std;
    #define lson k*2
    #define rson k*2+1
    #define M (t[k].l+t[k].r)/2
    #define INF 1008611111
    #define ll long long
    #define eps 1e-15
    int getmin(char T[])
    {
        int i=0,j=1,k=0;
        int tlen=strlen(T);
        while(i<tlen&&j<tlen&&k<tlen)
        {
            int t=T[(i+k)%tlen]-T[(j+k)%tlen];
            if(!t)
                k++;
            else
            {
                if(t>0)
                    i=i+k+1;
                else
                    j=j+k+1;
                if(i==j)
                    j++;
                k=0;
            }
        }
        return min(i,j);
    }
    int main()
    {
        int test,i,j,n,x;
        char s[100005];
        scanf("%d",&test);
        while(test--)
        {
            scanf("%d%s",&x,s);
            printf("%d\n",getmin(s));
        }
        return 0;
    }