hdu 3374 String Problem (字符串的最小/大表示法+kmp)

  1/* ***********************************************
  2Author :111qqz
  3Created Time :2016年08月13日 星期六 03时22分47秒
  4File Name :code/hdu/3374.cpp
  5************************************************ */
  6#include <cstdio>
  7#include <cstring>
  8#include <iostream>
  9#include <algorithm>
 10#include <vector>
 11#include <queue>
 12#include <stack>
 13#include <set>
 14#include <map>
 15#include <string>
 16#include <cmath>
 17#include <cstdlib>
 18#include <deque>
 19#include <ctime>
 20#define fst first
 21#define sec second
 22#define lson l,m,rt<<1
 23#define rson m+1,r,rt<<1|1
 24#define ms(a,x) memset(a,x,sizeof(a))
 25typedef long long LL;
 26#define pi pair < int ,int >
 27#define MP make_pair
 28using namespace std;
 29const double eps = 1E-8;
 30const int dx4[4]={1,0,0,-1};
 31const int dy4[4]={0,-1,1,0};
 32const int inf = 0x3f3f3f3f;
 33const int N=1E6+7;
 34char s[N],tmp[N];
 35int minRep(char *s)
 36{
 37    int n = strlen(s);
 38    int i = 0;
 39    int j = 1;
 40    int k = 0;
 41    while (i<n&&j<n&&k<n)
 42    {
 43	int t = s[(i+k)%n]-s[(j+k)%n];
 44	if (t==0) k++;
 45	else
 46	{
 47	    if (t>0)
 48		i+=k+1;
 49	    else j +=k+1;
 50	    if (i==j) j++;
 51	    k = 0 ;
 52	}
 53    }
 54    return i<j?i:j;
 55}
 56int maxRep(char *s)
 57{
 58    int n = strlen(s);
 59    int i = 0 ;
 60    int j = 1 ;
 61    int k = 0 ; 
 62    while (i<n&&j<n&&k<n)
 63    {
 64	int t = s[(i+k)%n]-s[(j+k)%n];
 65	if (t==0) k++;
 66	else
 67	{
 68	    if (t<0)
 69		i+=k+1;
 70	    else j+=k+1;
 71	    if (i==j) j++;
 72	    k = 0 ;
 73	}
 74    }
 75    return i<j?i:j;
 76}
 77int nxt[N];
 78void getnxt(char *s)
 79{
 80    int n = strlen(s);
 81    int i = 0 ;
 82    int j = -1;
 83    nxt[0] = -1;
 84    while (i<n)
 85	if (j==-1||s[i]==s[j]) nxt[++i]=++j;
 86	else j = nxt[j];
 87}
 88int main()
 89{
 90	#ifndef  ONLINE_JUDGE 
 91	freopen("code/in.txt","r",stdin);
 92  #endif
 93	while (scanf("%s",s)!=EOF)
 94	{
 95	    int len = strlen(s);
 96	    int k = minRep(s);
 97	    int cnt = 0;
 98	    ms(tmp,0);
 99	    for ( int i = k ; cnt < len ; i++,cnt++)
100		tmp[cnt] = s[i%len];
101	    getnxt(tmp);
102	    printf("%d %d ",k+1,len/(len-nxt[len]));
103	    k = maxRep(s);
104	    cnt = 0 ;
105	    ms(tmp,0);
106	    for ( int i = k ; cnt < len ; i++,cnt++)
107		tmp[cnt] = s[i%len];
108	    getnxt(tmp);
109	    printf("%d %d\n",k+1,len/(len-nxt[len]));
110	}
111  #ifndef ONLINE_JUDGE  
112  fclose(stdin);
113  #endif
114    return 0;
115}