[UVALive3026] Period 字符串

本文主要是介绍[UVALive3026] Period 字符串，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

利用KMP的失配函数判断周期

充要条件i % (i - f[i]) == 0 并且i不能为0

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<iostream>
#define SF scanf
#define PF printf
#define max(a, b) ((a) < (b) ? (b) : (a))
using namespace std;
typedef long long LL;
const int MAXN = 1000000;
int f[MAXN+10];
char s[MAXN+10];
void GetFail(char *P, int *f)
{f[0] = f[1] = 0;int Len = strlen(P);for(int i = 1; i < Len; i++){int j = f[i];while(j && P[i] != P[j]) j = f[j];f[i+1] = (P[i] == P[j]) ? j + 1 : 0;}
}
int main()
{int kase = 0, n;while(SF("%d", &n) && n){SF("%s", s);GetFail(s, f);printf("Test case #%d\n", ++kase);for(int i = 2; i <= n; i++) if(f[i] > 0 && i % (i - f[i]) == 0) PF("%d %d\n", i, i / (i - f[i]));puts("");}
}

这篇关于[UVALive3026] Period 字符串的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---