KMP-(POJ 2752)Seek the Name, Seek the Fame

缺乏、安全感 2022-05-17 01:18 110阅读 0赞

*  # KMP-(POJ 2752)Seek the Name, Seek the Fame #

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

*  ## 题目链接：[11:Seek the Name, Seek the Fame][11_Seek the Name_ Seek the Fame] ##
 *  ## 基础： ##

### **KMP算法** ###

给个传送门，分享下KMP：[ 串的模式匹配算法-KMP算法][_-KMP]

*  ## 思路： ##

题目要求的是***所有***能与**给定串**的**前缀和后缀**相匹配的子串长度

而规律是从Next数组后往前递归，求得最大符合要求子串（不包括原串），**Next\[len\]的值指向的下一Next值也是符合要求子串的长度，直到Next值小于等于0**

KMP性质：下标为**Index**的**Next值**表示的是以**Str\[Index-1\]结尾的子串**与**Str**的匹配程度，所以**Next数组要求到下标为Len，才能获得结尾为Str\[Len-1\]的串与Str的匹配程度**

![70][]

*  ## 代码： ##

#include<iostream>	
    #include<cstring>	
    using namespace std;
    //poj 2752
    #define MAXSIZE 400005
    
    int Next[MAXSIZE];
    int Answer[MAXSIZE];
    int len;
    
    void KMP(char Str[])
    {
    	int i = 0, k = -1;
    	Next[0] = -1;
    	while (i < len)
    	{
    		if (k == -1 || Str[i] == Str[k])
    		{
    			++i;
    			++k;
    			Next[i] = k;
    		}
    		else
    			k = Next[k];
    	}
    }
    
    int main()
    {
    	char Str[MAXSIZE];
    	
    	while (cin >> Str)
    	{
    		len = strlen(Str);
    		KMP(Str);
    		
    		int n = 0, i = len;
    		Answer[0] = len;	//最长符合情况的子串是本身！
    		while (Next[i] > 0)
    		{
    			i = Next[i];		//Next[i]表示符合要求子串长度
    			Answer[++n] = i;	//记录长度
    		}
    		for (int i = n; i >= 0; i--)
    		{
    			cout << Answer[i] << " ";
    		}
    		cout << endl;
    	}
    	return 0;
    }

[11_Seek the Name_ Seek the Fame]: http://dsalgo.openjudge.cn/string/11/
[_-KMP]: https://blog.csdn.net/SZU_Crayon/article/details/80385210
[70]: /images/20220517/2c65cc0139524797a71b172c40ed1641.png