總時間限制: 3000ms
記憶體限制: 65536kB
描述
給定兩個字串a和b,我們定義ab為他們的連接，例如，如果a=”abc”
而b=”def”， 則ab=”abcdef”，
如果我們將連接考慮成乘法，一個非負整數的乘方將用一種通常的方式定義：a0=””(空字串)，a(n+1)=a*(a^n)，
輸入
每一個測驗樣例是一行可列印的字符作為輸入，用s表示，s的長度至少為1，且不會超過一百萬，最后的測驗樣例后面將是一個點號作為一行，
輸出
對于每一個s，你應該列印最大的n，使得存在一個a，讓s=a^n
樣例輸入
abcd
aaaa
ababab .
樣例輸出
1
4
3
提示
本問題輸入量很大，請用scanf代替cin，從而避免超時，
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int MAXM = 1000005;
char P[MAXM];
int N[MAXM];
int m;
int main()
{
while (scanf("%s", P) == 1) {
if ((m = strlen(P)) == 1 && P[0] == '.')
break;
int j = 0, t = N[0] = -1;
while (j < m) {
if (t == -1 || P[t] == P[j])
N[++j] = ++t;
else
t = N[t];
}
int len = m - t;
printf("%d\n", m % len ? 1 : m / len);
}
system("pause");
return 0;
}
總時間限制: 3000ms 記憶體限制: 65536kB
描述
一個字串的前綴是從第一個字符開始的連續若干個字符，例如"abaab"共有5個前綴，分別是a, ab, aba, abaa, abaab，
我們希望知道一個N位字串S的前綴是否具有回圈節，換言之，對于每一個從頭開始的長度為 i （i 大于1）的前綴，是否由重復出現的子串A組成，即 AAA…A （A重復出現K次,K 大于 1），如果存在，請找出最短的回圈節對應的K值（也就是這個前綴串的所有可能重復節中，最大的K值），
輸入
輸入包括多組測驗資料，每組測驗資料包括兩行，
第一行包括字串S的長度N（2 <= N <= 1 000 000），
第二行包括字串S，
輸入資料以只包括一個0的行作為結尾，
輸出
對于每組測驗資料，第一行輸出 "Test case #“ 和測驗資料的編號，
接下來的每一行，輸出前綴長度i和重復測數K，中間用一個空格隔開，前綴長度需要升序排列，
在每組測驗資料的最后輸出一個空行，
樣例輸入
3
aaa
12
aabaabaabaab
0
樣例輸出
Test case #1
2 2
3 3
Test case #2
2 2
6 2
9 3
12 4
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int MAXN = 1000005;
int N[MAXN], n;
char s[MAXN];
int main()
{
int cnt = 0;
while (cin >> n) {
if (n == 0)
break;
printf("Test case #%d\n", ++cnt);
scanf("%s", s);
n = strlen(s);
int j = 0, t = N[0] = -1;
while (j < n) {
if (t == -1 || s[j] == s[t]) {
N[++j] = ++t;
int len = j - t;
if (j % len == 0 && len != j)
printf("%d %d\n", j, j/len);
}
else
t = N[t];
}
printf("\n");
}
system("pause");
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/233906.html
標籤：其他