HDU 3374 String Problem（最大最小表示法模板+KMP+next数组的运用）

忘是亡心i 2022-06-09 00:51 128阅读 0赞

Give you a string with length N, you can generate N strings by left shifts. For example let consider the string “SKYLONG”, we can generate seven strings:  
String Rank  
SKYLONG 1  
KYLONGS 2  
YLONGSK 3  
LONGSKY 4  
ONGSKYL 5  
NGSKYLO 6  
GSKYLON 7  
and lexicographically first of them is GSKYLON, lexicographically last is YLONGSK, both of them appear only once.  
Your task is easy, calculate the lexicographically fisrt string’s Rank (if there are multiple answers, choose the smallest one), its times, lexicographically last string’s Rank (if there are multiple answers, choose the smallest one), and its times also.

Input

Each line contains one line the string S with length N (N <= 1000000) formed by lower case letters.

Output

Output four integers separated by one space, lexicographically fisrt string’s Rank (if there are multiple answers, choose the smallest one), the string’s times in the N generated strings, lexicographically last string’s Rank (if there are multiple answers, choose the smallest one), and its times also.

Sample Input

abcder
    aaaaaa
    ababab

Sample Output

1 1 6 1
    1 6 1 6
    1 3 2 3

题解：

题意：

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

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

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

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

同理得出最大表示法

该题就是给你一个串，让你求最小表示法的开始位置（从1开始）,和数量，最大表示法的开始位置和数量

思路：

最大最小表示法直接套模板，至于数量就判断串是不是循环串，也就是设串长为len，len%(len-next\[len\]）为0就是循环串，最大最小表示法数量就是len/(len-next\[len\]），否则不是循环串就为1

代码：

#include<algorithm>
    #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 Next[1000005];
    void init(char T[])
    {
        int i,j;
        i=0,j=-1;
        Next[0]=-1;
        while(T[i])
        {
            if(j==-1||T[i]==T[j])
            {
                i++;
                j++;
                Next[i]=j;
            }
            else
                j=Next[j];
        }
    }
    int getminmax(int flag,char word[])  //最小最大表示法0、1
    {
        int i=0,j=1,k=0;
        int wlen=strlen(word);
        while(i<wlen&&j<wlen&&k<wlen)
        {
            int t=word[(i+k)%wlen]-word[(j+k)%wlen];
            if(!t) k++;
            else
            {
                if(flag==0)
                {
                    if(t>0) i=i+k+1;
                    else    j=j+k+1;
                }
                else
                {
                    if(t>0) j=j+k+1;
                    else    i=i+k+1;
                }
                if(i==j)    j++;
                k=0;
            }
        }
        return i<j?i:j;
    }//返回的是从0开始的位置
    int main()
    {
        int i,j,n,t,len,minn,maxx;
        char s[1000005];
        while(scanf("%s",s)!=EOF)
        {
            init(s);
            len=strlen(s);
            t=1;
            if(len%(len-Next[len])==0)//判断是否为循环串
                t=len/(len-Next[len]);
            minn=getminmax(0,s);
            maxx=getminmax(1,s);
            printf("%d %d %d %d\n",minn+1,t,maxx+1,t);
        }
        return 0;
    }