Note: This article is available in Chinese only. 本文暂无英文版本。
View original
hdu 3374 题目链接 题意：给出一个循环字符串，问最小表示出现的位置以及次数，最大表示出现的位置以及次数。 思路：之前只写过最小表示。。最大表示其实是一样的。。。把不等式方向变号即可。。。对于出现的次数。。。其实就等同于这个字符串是由几个子串组成。。。跑一遍kmp。。答案为len-nxt[len]，1A
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}