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

ゞ浴缸里的玫瑰 2022-05-17 08:51 145阅读 0赞

*  # KMP-(POJ 2406)Power Strings\[字符串乘方\] #

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

*  ## 题目链接：[Power Strings][] ##
 *  ## 思路：最小循环节 ##

看到乘方，很明显是**求给定字符串由它的最小循环子串循环得到的次数**

那就是求出NEXT数组，再而求出**最小循环节长度：Len-NEXT\[Len\]**

有三种情况，分两类

**①给定字符串循环子串是其本身：乘方等于1**

**a.NEXT\[Len\]=0 栗如：abcd**

**b.NEXT\[Len\]!=0,but Len%(Len-NEXT\[Len\]) != 0**：**所求循环节长度与字符串长度不成倍数，例如abbbabb**，求得的可能最小循环节为abbb，很明显不是真正的循环子串，***真正的最小循环节应为本身：abbbabb***

**②子串为最小循环节**

**c.Len%(Len-NEXT\[Len\])=0**，那么循环次数也就是乘方为 **Len/(Len-NEXT\[Len\])**

*  ## 题目基础：KMP-NEXT数组的性质 ##

**KMP算法-求NEXT数组：[ 串的模式匹配算法-KMP算法][_-KMP]**

**最小循环节：[KMP-(HDU1358)Period\[前缀中的周期\]][KMP-_HDU1358_Period]**

*  ## **代码：** ##

#include<iostream>	
    #include<cstring>	
    using namespace std;
    //KMP POJ 2406
    #define MAX_Length 1000005
    
    int Next[MAX_Length];
    int len;
    char Str[MAX_Length];
    
    
    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;
    		}
    		else
    			j = Next[j];
    	}
    }
    
    int main()
    {
    	while (cin >> Str && Str[0] != '.')
    	{
    		len = strlen(Str);
    		KMP();
    		int Min_Period_Len = len - Next[len];		//求出最小循环节长度
    		if (Min_Period_Len == len || len % Min_Period_Len)		//循环节是本身的情况，那么乘方是1
    			cout << "1" << endl;
    		else
    		{
    			int Period_Num = len / Min_Period_Len;		//求出循环次数
    			cout << Period_Num << endl;
    		}
    	}
    	return 0;
    }

[Power Strings]: http://poj.org/problem?id=2406
[_-KMP]: https://blog.csdn.net/SZU_Crayon/article/details/80385210
[KMP-_HDU1358_Period]: https://blog.csdn.net/SZU_Crayon/article/details/81414570