KMP-(HDU1358)Period[前缀中的周期]

矫情吗；* 2022-05-17 01:50 153阅读 0赞

*  # KMP-(HDU1358)Period #

--------------------

*  ## 题目链接：[9:前缀中的周期][9] ##
 *  ## **KMP基础：** ##

给个传送门复习下KMP：[串的模式匹配算法-KMP算法][-KMP]

*  ## 思路： ##

给定Next\[i\]，**Next\[i\]指向的总是上一循环节*后面*的一个字符**，**所以上一循环节末尾为Next\[i\]-1**

**当前循环节的末尾为i-1**，易得当前循环节长度：**（i-1）-（Next\[i\]-1）=i-Next\[i\]**

***由题意已经假设0~i-1的串是循环的***，所以要判断循环是否成立，只要满足**长度 i 是当前循环节长度的倍数**

即：**i%（Next\[i\]-1）==0**，同时必须在Next\[i\]！=0 前提下（不重复的串Next数组中很多0）

*  ## 总结： ##

对于Next数组，满足 **i % ( i - Next\[i\] ) == 0 && Next\[i\] != 0**说明找到当前循环节

**循环节长度：****i-Next\[i\]**

**循环次数：i/(i-Next\[i\])**

*  ## 代码： ##

#include<iostream>	
    #include<cstring>	
    using namespace std;
    //HDU1358  Period
    #define MAXSIZE 1000005
    int Next[MAXSIZE];
    char Str[MAXSIZE];
    int Len;
    
    void KMP()
    {
    	int j = -1, k = 0;
    	Next[0] = -1;
    	while (k < Len)
    	{
    		if (j == -1 || Str[j] == Str[k])
    		{
    			j++;
    			k++;
    			Next[k] = j;    //j==Next[k]
    			if (k % (k - j) == 0 && j != 0)
    			{
    				cout << k << " " << k / (k - j) << endl;
    			}
    		}
    		else
    			j = Next[j];
    	}
    }
    
    int main()
    {
    	int Case = 0;
    	while (cin >> Len && Len)
    	{
    
    		cin >> Str;
    		cout << "Test case #" << ++Case << endl;
    		KMP();
    		cout << endl;
    	}
    	return 0;
    }

*  ## 参考： ##

[Jack Ge for ACM- KMP算法 —— next 数组的应用 --- 前缀中最小循环节，最大重复次数][Jack Ge for ACM- KMP_ _ next _ ---]

他山之石，我之师，共勉

[9]: http://dsalgo.openjudge.cn/string/9/
[-KMP]: https://blog.csdn.net/SZU_Crayon/article/details/80385210
[Jack Ge for ACM- KMP_ _ next _ ---]: http://www.cnblogs.com/jackge/archive/2013/01/05/2846006.html