String Problem（KMP+最小表示法）- HDU 3374

Problem Description

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

概译：一个字符串循环一下，每个位置都当一次头（即循环同构），求最小和最大字典序的那两个串的起始位置和总共出现次数。译的不好，不过原文其实很好懂。

输出：最小字典序的rank，出现次数，最大字典序的rank，出现次数

求rank是典型的用最小表示法来求，而求出现的次数是循环节的次数，没有循环节就1次呗。求循环节需要使用到kmp算法中next数组的递推过程。

至于kmp算法和最小表示法，都是字符串的相关算法。个人感觉讲起来是很难懂的，不懂的同学希望能够自学一下，按照博客上的思路及代码自己画一画会好很多。这道题目和这两个算法，AlphaWA也是听了大佬的讲课介绍然后新学的（被校友认出系列），刚开始肯定感觉不透彻，不熟悉原理，不过以后慢慢变强了就会加深理解了吧，学习的过程好像一般都是这样子的（我胡扯的）。

代码如下：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define maxn 1000010
using namespace std;

char s[maxn];
int Next[maxn];

void getnext(char *s,int len)//求next数组以获得循环节长度 
{
    Next[0]=Next[1]=0;
    for(int i=1;i<len;i++)
    {
        int j=Next[i];
        while(j&&s[i]!=s[j]) j=Next[j];
        Next[i+1]=s[i]==s[j]?j+1:0;
    }
}

int express(char *s,int len,int flag)//最小表示法求最小字典序的循环同构的起始位置 
{
    int i=0,j=1,k=0;
    while(i<len&&j<len&&k<len)
    {
        int t=s[(i+k)%len]-s[(j+k)%len];
        if(flag)//最小表示 
        {
            if(!t) k++;
            else if(t>0) i=i+k+1,k=0;
            else j=j+k+1,k=0;
            if(i==j) j++;
        }
        else//最大表示 
        {
            if(!t) k++;
            else if(t<0) i=i+k+1,k=0;
            else j=j+k+1,k=0;
            if(i==j) j++;   
        }
    }
    return min(i,j);
}

int main()
{
    while(~scanf("%s",s))
    {
        int len=strlen(s);
        int rank1=express(s,len,1)+1,rank2=express(s,len,0)+1;//flag设为1是求最小字典序，设为0是求最大 
        getnext(s,len);//kmp里面求next数组的方法 
        int cnt=len/(len-Next[len]);//据说个数就是循环节的个数，最大最小都是一样的 
        printf("%d %d %d %d\n",rank1,cnt,rank2,cnt);
    }
    return 0;
}