KMP字符串匹配算法的原理与实现

爱被打了一巴掌 2022-08-02 05:48 145阅读 0赞

[![Flag Counter][]][Flag Counter 1]

KMP算法是一种改进的字符串匹配算法，由D.E.Knuth与V.R.Pratt和J.H.Morris同时发现，因此人们称它为克努特——莫里斯——普拉特操作（简称KMP算法）。

KMP算法的关键是利用匹配失败后的信息，尽量减少模式串与主串的匹配次数以达到快速匹配的目的。即确定下一次应该从那个位置重新开始匹配。

char\*obj = "cbcba";

char\*src = "sdcbcbcba";

要在src中寻找obj，过程如下：

从src第0位开始匹配，s匹配失败，移动1位，

从d开始匹配，d匹配失败，移动1位，

接着从src第2位c开始，匹配，继续b，匹配，继续c，匹配，继续b，匹配，继续c，不匹配，

KMP算法关键点就在这里，要移动最大的距离，在这里是2位，即从src第二位移动到第四位，下次从第四位的c开始匹配。

对于一个要查找的目标字符串，每次在哪一位匹配失败后要移动的最大距离可以提前算出来，存到一个数组里，匹配时直接查找就行。

纯粹自己实现，代码有些丑陋，呵呵

// KMP.cpp : 定义控制台应用程序的入口点。
    //
    
    #include "stdafx.h"
    #include<iostream>
    using namespace std;
    
    int*kk;
    int*kkk;
    
    int KMP(char*src, char*obj)
    {
    	int k1 = 0; 
    	int k2 = 0;
    	int len1 = strlen(src);
    	int len2 = strlen(obj);
    	while (k1 < len1)
    	{
    		if (src[k1] != obj[0])
    		{
    			++k1;
    			continue;
    		}
    		while (k2 < len2+1&&k1+k2 < len1+1)
    		{
    			if (k2 == len2)
    				return k1;
    			if (src[k1 + k2] == obj[k2])
    				++k2;
    			else 
    				if (kkk[k2] == 1)
    				{
    				k1 = k1 + kk[k2];
    				k2 = 0;
    				continue;
    				}
    				else
    					if (obj[k2 - kk[k2]] == src[k1 + k2])
    					{
    				k1 = k1 + kk[k2];
    				k2 = 0;
    				continue;
    					}
    					else
    					{
    						k1 = k1 + k2 + 1;
    						k2 = 0;
    						continue;
    					}
    
    		}
    	}
    
    	return -1;
    
    }
    
    
    int* shift(char*obj)
    {
    	int len = strlen(obj);
    	kk = new int[len];
    	kkk = new int[len];
    	for (int i = 0; i < len; i++)
    	{
    		kkk[i ]= 0; 
    	}
    	kk[0] = 1;
    	if (len > 1)
    	{
    		if (obj[0] == obj[1])
    		{
    			kk[1] = 2;
    			kkk[1] = 1;
    		}
    		else
    			kk[1] = 1;//条件是src与obj第1位匹配的字符等于obj第0个字符，否则kk[1]=2，这由匹配时的src决定
    	}
    	
    
    	int k = 2;
    	int n = 0;
    	int m = 1;
    	while (k < len)
    	{
    		bool flag = false;
    		bool flag1 = false;
    		while (m<k)
    		{
    			
    			if (obj[m] != obj[n])
    			{
    				++m;
    				continue;
    			}
    			while (obj[m] == obj[n])
    			{
    				flag1 = true;
    				if (m == k - 1)
    				{
    					flag = true;
    					break;
    				}
    				++m;
    				++n;
    			}
    			if (flag)
    				break;
    		}
    		if (!flag1)
    			if (obj[k] == obj[0])
    			{
    			kk[k] = k + 1;//此时直接后移，src无需判断
    			kkk[k] = 1;
    			n = 0;
    			m = 1;
    			++k;
    			continue;
    			}
    		if (obj[k] == obj[n + 1])
    		{
    			kk[k] = k + 1;//此时直接后移，src无需判断
    			kkk[k] = 1;
    			n = 0;
    			m = 1;
    			++k;
    			continue;
    		}
    		if (flag)
    			kk[k] = k - 1 - n;//此处假设src与obj第k位匹配的字符等于obj第n+1个字符，否则kk[k]=k+1，kmp匹配时需做判断
    		else
    			kk[k] = k;//此处假设src与obj第k位匹配的字符等于obj第0个字符，否则kk[k]=k+1，kmp匹配时需做判断
    		n = 0;
    		m = 1;
    		++k;
    
    	}
    
    	return kk;
    }
    
    
    
    
    int _tmain(int argc, _TCHAR* argv[])
    {
    	//char*obj = "cbcba";
    	//char*src = "sdcbcbcba";
    	//char*src = "abacaabacabacabaabb";
    	//char*obj = "abacab";
    	char*src = "BBC ABCDAB ABCDABCDABDE";
    	char*obj = "ABCDABD";
    	int len = strlen(obj);
    	shift(obj);
    	for (int i = 0; i < len; i++)
    		cout << kk[i] << endl;
    	cout << endl;
    	for (int i = 0; i < len; i++)
    		cout << kkk[i] << endl;
    	cout << KMP(src, obj) << endl;
    	system("pause");
    	return 0;
    }

[Flag Counter]: /images/20220731/ad04b8abe934446fb2126d4623f25c13.png
[Flag Counter 1]: http://s11.flagcounter.com/more/RPv