poj 2406 KMP算法求字符串的最小周期

痛定思痛。 2022-07-26 05:23 187阅读 0赞

[点击打开链接][Link 1]

题意:求字符串的最小周期;

分析: 利用KMP算法求Next\[\]数组的过程可以求得最小周期, 我对KMP算法的Next\[\]数组的求法过程还没有理解透彻, 等以后做题做多了再来看一下.

#include<bitset>
    #include<map>
    #include<vector>
    #include<cstdio>
    #include<iostream>
    #include<cstring>
    #include<string>
    #include<algorithm>
    #include<cmath>
    #include<stack>
    #include<queue>
    #include<set>
    #define inf 0x3f3f3f3f
    #define mem(a,x) memset(a,x,sizeof(a))
    #define F first
    #define S second
    using namespace std;
    
    typedef long long ll;
    typedef unsigned long long ull;
    typedef pair<int,int> pii;
    
    inline int in()
    {
        int res=0;char c;int f=1;
        while((c=getchar())<'0' || c>'9')if(c=='-')f=-1;
        while(c>='0' && c<='9')res=res*10+c-'0',c=getchar();
        return res*f;
    }
    const int N=1000010;
    
    char a[N];
    int Next[N];
    int main()
    {
        while(1)
        {
            scanf("%s",a);
            int n=strlen(a);
            if(n==1 && *a=='.') return 0;
            Next[0]=-1;
            int k=-1,j=0;
            while(j<n)
            {
                if(k==-1 || a[j]==a[k]) Next[++j]=++k;
                else k=Next[k];
            }
            j=n-Next[n];   //利用Next[n]的失配转移位置,不是n-1的
            if(n%j==0) printf("%d\n",n/j);
            else puts("1");
    
        }
        return 0;
    }

[Link 1]: http://http://poj.org/problem?id=2406

发表评论取消回复

表情：

评论列表（有 0 条评论，187人围观）

还没有评论，来说两句吧...

相关阅读

相关 POJ 2406

Description Given two strings a and b we define a\b to be their concatenation. For exam

蔚落/ 2022年08月21日 11:58/ 0 赞/ 16 阅读

相关 poj 2406 Power Strings【kmp】

Power Strings Description Given two strings a and b we define a\b to be their concaten

电玩女神/ 2022年08月21日 02:17/ 0 赞/ 25 阅读

相关 poj 2406 KMP算法求字符串的最小周期

[点击打开链接][Link 1] 题意:求字符串的最小周期; 分析: 利用KMP算法求Next\[\]数组的过程可以求得最小周期, 我对KMP算法的Next\[\]数

痛定思痛。/ 2022年07月26日 05:23/ 0 赞/ 188 阅读

相关 POJ 2406 Power Strings（KMP+最小循环节）

Given two strings a and b we define a\b to be their concatenation. For example, if a = "

电玩女神/ 2022年06月10日 14:08/ 0 赞/ 195 阅读

相关 KMP-(POJ 2406)Power Strings[字符串乘方]

KMP-(POJ 2406)Power Strings\[字符串乘方\] -------------------- 题目链接：[Power Strings

ゞ浴缸里的玫瑰/ 2022年05月17日 08:51/ 0 赞/ 160 阅读

相关 POJ 2406 Power Strings——————KMP next数组的利用

Power Strings <table> <tbody> <tr> <td> <div> Language:Default

灰太狼/ 2022年05月16日 09:15/ 0 赞/ 164 阅读

相关 kmp2-HDU1358 HUST1010 POJ2406 POJ2752

HDU1358 [http://acm.hdu.edu.cn/showproblem.php?pid=1358][http_acm.hdu.edu.cn_showprob

Dear 丶/ 2022年05月14日 11:25/ 0 赞/ 152 阅读

相关【HDU 1358】Period（KMP求字符串周期）

题目链接：[http://acm.hdu.edu.cn/showproblem.php?pid=1358][http_acm.hdu.edu.cn_showproblem.ph

骑猪看日落/ 2022年02月14日 02:09/ 0 赞/ 252 阅读

相关 poj2406

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][] /\Poj2406题解： if (len % (len \

た入场券/ 2021年12月22日 10:07/ 0 赞/ 162 阅读

相关 poj(2406)(kmp)

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][] 1 // kmp算法 2 \include " io

小咪咪/ 2021年12月22日 09:45/ 0 赞/ 220 阅读