KMP算法代码实现

墨蓝 2022-08-05 11:17 210阅读 0赞

有关KMP算法，这里有篇博客讲解的特别好，博客链接为：

[http://blog.csdn.net/tukangzheng/article/details/38438481][http_blog.csdn.net_tukangzheng_article_details_38438481]

**下面是我实现的代码：**

#include <iostream>
    #include <vector>
    #include <stdlib.h>
    #include <stack>
    
    using namespace std;
    
    /* 得到字符串的next数组 */
    int getNextArray(char* str, int* next)
    {
    	int len = 0;
    	
    	int k = -1;
    	int j = 0;
    	next[0] = -1;
    
    	if(NULL == str)
    	{
    		return -1;
    	}
    
    	len = strlen(str);
    	while(j < len-1)
    	{
    		if(k == -1 || str[k] == str[j])
    		{
    			k++;
    			j++;
    			next[j] = k;
    		}
    		else
    		{
    			k = next[k];
    		}
    	}
    	return 0;
    }
    
    /* 通过KMP算法进行字符串匹配 */
    bool kmpSearch(char* s, char* p, int* next)
    {
    	if(NULL == s || p == NULL)
    	{
    		if(s == NULL)
    		{
    			return false;
    		}
    		else if(p == NULL)
    		{
    			return true;
    		}
    	}
    
    	int len_s = strlen(s);
    	int len_p = strlen(p);
    
    	int index_s = 0;
    	int index_p = 0;
    
    	while(index_s < len_s && index_p < len_p)
    	{
    		/* index_p == -1,或者没有匹配到的时候 */
    		if(index_p == -1 || s[index_s] == p[index_p])
    		{
    			++index_s;
    			++index_p;
    		}
    		else
    		{
    			index_p = next[index_p];
    		}
    	}
    
    	if(index_p == len_p)
    	{
    		return true;
    	}
    
    	return false;
    }
    int main()
    {
    	char str[] = {"abcabd"};
    	int next[10] = {0};
    	int i = 0;
    
    	getNextArray(str,next);
    	for(i = 0; i < strlen(str); i ++)
    	{
    		cout << next[i] << " ";
    	}
    	cout << endl;
    
    	if(kmpSearch("abcabcd","abcs",next) == true)
    	{
    		cout << "true" << endl;
    	}
    	else
    	{
    		cout << "false" << endl;
    	}
    
    		
    
    	return 0;
    }

[http_blog.csdn.net_tukangzheng_article_details_38438481]: http://blog.csdn.net/tukangzheng/article/details/38438481