kmp2-HDU1358 HUST1010 POJ2406 POJ2752

Dear 丶 2022-05-14 11:25 162阅读 0赞

# HDU1358 #

[http://acm.hdu.edu.cn/showproblem.php?pid=1358][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][http_www.hustoj.org_problem_1010]

读错题了，B是减下来的那一堆，那就好做了。找最短循环节就可以了。（循环节：从某一位起向右进行到某一位止的一节数字循环出现，首尾衔接，称这种小数为[循环小数][Link 1]，这一节数字称为循环节。）

#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][http_poj.org_problem_id_2406]

大意：给出一个字符串 问它最多由多少相同的字串组成

如 abababab由4个ab组成

最小循环节

ababab next\[6\] = 4; 即

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][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;
    }

[http_acm.hdu.edu.cn_showproblem.php_pid_1358]: http://acm.hdu.edu.cn/showproblem.php?pid=1358
[http_www.hustoj.org_problem_1010]: http://www.hustoj.org/problem/1010
[Link 1]: https://baike.baidu.com/item/%E5%BE%AA%E7%8E%AF%E5%B0%8F%E6%95%B0/5890332
[http_poj.org_problem_id_2406]: http://poj.org/problem?id=2406
[http_poj.org_problem_id_2752]: http://poj.org/problem?id=2752