记录
18:26 2024-2-22
http://poj.org/problem?id=1961
利用KMP构造next数组，其实next数组就是方便于找到下一个应该比较的字符，或者说是不动目标字符，移动查找字符，这里面利用next数组就可以很快捷的移动
这道题是利用next字符，给出证明的结果是
当 i - next[i] 能整除 i时， S[1 ~ i - next[i]]就是 S[1 ~ i]的最小循环元
同理 对 i - next[next[i]] 能整除时，S[1 ~ i - next[next[i]]] 就是次小循环元，可以以此找到最大循环元
next下标从1开始
点击查看代码
#include<iostream>
#include<vector>
#include<stdio.h>
#include<string.h>
using namespace std;
const int INF = 0x3f3f3f3f;
const int MAXN = 1000005;
int N;
int T = 1;
int nxt[MAXN];
char str[MAXN];
//下标从1开始
void calc_next() {
nxt[1] = 0;
for (int i = 2, j = 0; i <= N; i++) {
while (j > 0 && str[i] != str[j+1]) j = nxt[j];
if (str[i] == str[j+1]) j++;
nxt[i] = j;
}
}
int main() {
while (cin >> N && N != 0) {
scanf("%s", str + 1);
calc_next();
printf("Test case #%d\n", T);
T++;
for(int i = 2; i <= N; i++) {
if(i % (i - nxt[i]) == 0 && i / (i - nxt[i]) > 1) {
printf("%d %d\n", i, i / (i - nxt[i]) );
}
}
printf("\n");
}
}
next下标从0开始
点击查看代码
#include<iostream>
#include<vector>
#include<stdio.h>
#include<string.h>
using namespace std;
const int INF = 0x3f3f3f3f;
const int MAXN = 1000005;
int N;
int T = 1;
int nxt[MAXN];
char str[MAXN];
//下标从0开始
void calc_next() {
nxt[0] = -1;
for (int i = 1, j = -1; i < N; i++) {
while (j >= 0 && str[i] != str[j+1]) j = nxt[j];
if (str[i] == str[j+1]) j++;
nxt[i] = j;
}
}
int main() {
while (cin >> N && N != 0) {
scanf("%s", str);
calc_next();
printf("Test case #%d\n", T);
T++;
//如果从零开始 要变为i + 1
for(int i = 1; i < N; i++) {
if((i + 1) % (i - nxt[i]) == 0 && (i + 1) / (i - nxt[i]) > 1) {
printf("%d %d\n", (i + 1), (i + 1) / (i - nxt[i]) );
}
}
printf("\n");
}
}