# 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```

```#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;
} ```

0 条评论

• ### HDU6370：Werewolf 推理+拓扑排序 2018第六场杭电多校

"The Werewolves" is a popular card game among young people.In the basic game, th...

• ### 牛客小白月赛11D（分治、RMQ）

定义一个玄学节点叫做 R，每次操作读入 val ，执行 Insert(R,val)。

• ### #633 DIV2 题解

组样例，每组样例给一个， 代表个三角形按照菱形的样子尽可能的拼凑在一起(可以旋转)，如图所示

• ### ZOJ 3490 String Successor（模拟）

Time Limit: 2 Seconds Memory Limit: 65536 KB The successor to a string ca...

• ### HDU----（3294）Girls' research（manacher）

Girls' research Time Limit: 3000/1000 MS (Java/Others)    Memory Limit: 65535/3...

• ### HDU 4247 Pinball Game 3D(cdq 分治+树状数组+动态规划)

Pinball Game 3D Time Limit: 10000/5000 MS (Java/Others)    Memory Limit: 32768/...

• ### 11-散列2 Hashing (25分)

The task of this problem is simple: insert a sequence of distinct positive integ...

• ### 算法复杂度O(logn)详解

由于cnt每次在乘以2之后都会更加逼近n，也就是说，在有x次后，cnt将会大于n从而跳出循环，所以

• ### 桶排序的算法

思路：设数组的长度为len，创建三个长度为len+1的（桶）数组。将数组的元素根据大小放在不同的桶中，其中，必定有差值大于一个桶的差存在，故同一个桶中不可能出现...