kmp2-HDU1358 HUST1010 POJ2406 POJ2752
HDU1358
http://acm.hdu.edu.cn/showproblem.php?pid=1358
先构造出 next[] 数组，下标为 i，定义一个变量 j = i - next[i] 就是next数组下标和下标对应值的差，如果这个差能整除下标 i，即 i%j==0 ,则说明下标i之前的字符串（周期性字符串长度为 i）一定可以由一个前缀周期性的表示出来，这个前缀的长度为刚才求得的那个差，即 j，则这个前缀出现的次数为 i/j 。
-
#include <iostream>
-
#include <stdio.h>
-
using namespace std;
-
char a[1000010];
-
int next[1000010];
-
int n;
-
void GetNext() //获得a数列的next数组
-
{
-
int i=0,k=-1;
-
next[0] = -1;
-
while(i<n){
-
if(k==-1){
-
next[i+1] = 0;
-
i++;k++;
-
}
-
else if(a[i]==a[k]){
-
next[i+1] = k+1;
-
i++;k++;
-
}
-
else
-
k = next[k];
-
}
-
}
-
void DisRes(int num)
-
{
-
int j;
-
printf("Test case #%d\n",num);
-
for(int i=0;i<=n;i++){
-
if(next[i]==-1 || next[i]==0) //next[i]是-1或0的忽略，说明之前没有周期性前缀
-
continue;
-
j = i - next[i];
-
if(i%j==0) //能整除，说明存在周期性前缀
-
printf("%d %d\n",i,i/j); //输出这个前缀的长度和周期数
-
}
-
printf("\n");
-
}
-
int main()
-
{
-
int num = 0;
-
while(scanf("%d",&n)!=EOF){
-
if(n==0) break;
-
scanf("%s",a);
-
GetNext(); //获得next[]数组
-
DisRes(++num); //输出结果
-
}
-
return 0;
-
}
HUST 1010
http://www.hustoj.org/problem/1010
读错题了，B是减下来的那一堆，那就好做了。找最短循环节就可以了。（循环节：从某一位起向右进行到某一位止的一节数字循环出现，首尾衔接，称这种小数为循环小数，这一节数字称为循环节。）
-
#include<stdio.h>
-
#include<string.h>
-
#define N 1000005
-
char str[N];
-
int f[N];
-
void getFail(char *p, int *f)
-
{
-
int m=strlen(p);
-
f[0]=f[1]=0;
-
for(int i=1; i<m; ++i)
-
{
-
int j=f[i];
-
while(j && p[i]!=p[j])j=f[j];
-
f[i+1] = p[i]==p[j]?1+j:0;
-
}
-
}
-
int main()
-
{
-
while(scanf("%s",str)!=EOF)
-
{
-
int len=strlen(str);
-
getFail(str,f);
-
printf("%d\n",len-f[len]);
-
-
}
-
return 0;
-
}
POJ 2406
http://poj.org/problem?id=2406
大意：给出一个字符串 问它最多由多少相同的字串组成
如 abababab由4个ab组成
最小循环节
ababab next[6] = 4; 即
ababab
ababab
1~4位 与2~6位是相同的
那么前两位
就等于3、4位
3、4位就等于5、6位
……
所以 如果 能整除 也就循环到最后了
如果不能整除
就最后余下的几位不在循环内
-
#include <iostream>
-
#include <cstdio>
-
#include <cstring>
-
using namespace std;
-
-
const int maxn = 1000005;
-
-
int next[maxn];
-
-
void get(char *s) {
-
int l = strlen(s);
-
int j = 0, k = -1;
-
next[0] = -1;
-
while(j < l) {
-
if(k == -1 || s[j] == s[k]) {
-
next[++j] = ++k;
-
} else {
-
k = next[k];
-
}
-
}
-
}
-
char s[maxn];
-
-
int main() {
-
while(gets(s) ) {
-
if(strcmp(s,".") == 0) {
-
break;
-
}
-
get(s);
-
int ans = 1;
-
int l = strlen(s);
-
if(l % (l - next[l]) == 0) {
-
ans = l / (l - next[l]);
-
}
-
printf("%d\n", ans);
-
}
-
}
POJ2752
http://poj.org/problem?id=2752
大意：给定字符串S，求出S的所有可能相同前后缀的长度。比如：
"alala"的前缀分别为{"a", "al", "ala", "alal", "alala"}, 后缀分别为{"a", "la", "ala", "lala", "alala"}. 其中有{"a", "ala", "alala"}是相同的，即输入1,3,5.
思路：有了kmp算法的next数组（保存某段子串的相同前后缀的最大长度，不包括自身），可以从最长的相同前后缀开始考虑，对于串S，根据next[strlen(S)-1]得到的最长相同前后缀为S1,则再根据next[strlen(S1)-1]得到的S1的最长相同前后缀S2肯定也为S的相同前后缀。（通过画图可以很容易的证明）。
这样，通过不断的向前查找next数组，得到一系列的相同前后缀。下面证明这些前后缀包含了所有的相同前后缀：
由于我们得到的是一系列最长相同前后缀，假设有一个相同的前后缀Sk不属于这些通过next递推得到的前后缀集合，那么len(Sk)必定小于len(S1)，且Sk必定为S1的子串（通过画图很容易看出来）；此时若Sk是S1的最长前后缀，则与前提Sk不为某一子串的最长前后缀矛盾，那么Sk不是S1的最长前后缀，则可以退出len(Sk)必定小于S2，且Sk必定为S2的相同前后缀..... 数学归纳递推下去，可以知道Sk要么为某个Si的最长前后缀，要么len(Sk) = 0. 这样可以证明这些通过next数组递推得到的前后缀包含了所有的相同前后缀
-
#include <iostream>
-
#include <cstdio>
-
#include <cstring>
-
using namespace std;
-
-
int Next[400005];
-
char str[400005];
-
int ans[400005];
-
int cnt;
-
int len;
-
-
void getNext()
-
{
-
Next[0] = -1;
-
int i = 0, j = -1;
-
while (i < len)
-
{
-
if (j == -1 || str[i] == str[j])
-
{
-
++i;
-
++j;
-
Next[i] = j;
-
}
-
else j = Next[j];
-
}
-
}
-
-
int main()
-
{
-
while (scanf("%s", str) != EOF)
-
{
-
len = strlen(str);
-
getNext();
-
cnt = 0;
-
int t = Next[len - 1];
-
while (t != -1)
-
{
-
if (str[t] == str[len - 1]) ans[cnt++] = t + 1;
-
t = Next[t];
-
}
-
for (int i = cnt - 1; i >= 0; --i)
-
{
-
printf("%d ", ans[i]);
-
}
-
printf("%d\n", len);
-
}
-
return 0;
-
}
文章来源: fantianzuo.blog.csdn.net，作者：兔老大RabbitMQ，版权归原作者所有，如需转载，请联系作者。
原文链接：fantianzuo.blog.csdn.net/article/details/82492803
- 点赞
- 收藏
- 关注作者
评论（0）