POJ 1961

时间:2020-03-18 23:37:29   收藏:0   阅读:61

使用MP算法(而非KMP),以及字符串关于边界问题中出现的周期问题,详见本博客的文章字符串匹配章节

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;

const int maxn= 1e6+5;

char ar[maxn];
int nxt[maxn];

void Kmp(int m)
{
    int i= 0, j;
    j= nxt[0]= -1;

    while (i< m){
        while (j> -1 && ar[i]!= ar[j]){
            j= nxt[j];
        }
        nxt[++i]= ++j;
    }
}
int main()
{
    int kase=1, n, pd;

    while (EOF!= scanf("%d", &n) && n){
        printf("Test case #%d\n", kase++);
        scanf(" %s", ar);

        Kmp(n);

        for (int i= 2; i<= n; ++i){
            if (0== (i%(i-nxt[i]))){
                pd= i/(i-nxt[i]);
                if (1!= pd){
                    printf("%d %d\n", i, pd);
                }
            }
        }
        putchar('\n');
    }

    return 0;
}

原文:https://www.cnblogs.com/Idi0t-N3/p/12521027.html

评论(0
© 2014 bubuko.com 版权所有 - 联系我们:wmxa8@hotmail.com
打开技术之扣,分享程序人生!