kmp.cpp

KMP实现

#include <iostream>
#include <string>
using namespace std;



// 得到字符串的next数组
void GetNextArray(char *pstr, int *next)
{
  
   

                                      // 第一个字符的next值是-1,因为C中的数组是从0开始的
        next[0] = -1;
        for (int i = 0, j = -1; pstr[i]!='\0' ; )
        {
                // i是主串的游标,j是模式串的游标
                // 这里的主串和模式串都是同一个字符串
                if (-1 == j ||pstr[i] == pstr[j])        // 如果模式串游标已经回退到第一个字符
                                                         // 如果匹配成功
                {
                        // 两个游标都向前走一步
                        ++i;
                        ++j;
                        // 存放当前的next值为此时模式串的游标值
                        next[i] = j;
                }
                else                                                                // 匹配不成功j就回退到上一个next值
                {
                        j = next[j];
                }
        }

		for(i=0;pstr[i]!='\0';i++)
			cout<<next[i]<<" ";
}

int length(char *s)
{
	int length;
while(*s++) length++;
return length;
}
// KMP字符串模式匹配算法
// 输入: S是主串,T是模式串
// 输出: 如果匹配成功返回起始位置,否则返回-1
int KMP(char *S, char *T)
{
       
        int s_length=length(S);
		int t_length=length(T);
        if (s_length < t_length)
                return -1;
        cout<<"主串   "<<S<<endl;
		cout<<"模式串 "<<T<<endl;
       
      
        int *next = (int *)malloc(t_length * sizeof(int));
                                                            // 得到模式串的next数组
        GetNextArray(T, next);

        int i, j;
        for (i = 0, j = 0; i <s_length && j < t_length;)
        {
                // i是主串游标,j是模式串游标
                if (-1 == j ||S[i] == T[j])                     // 模式串游标已经回退到第一个位置                        // 当前字符匹配成功
                {
                        // 满足以上两种情况时两个游标都要向前进一步
                        ++i;
                        ++j;
                }
                else                                                //  匹配不成功,模式串游标回退到当前字符的next值
                {
                        j = next[j];
                }
        }

        free(next);

        if (j >= t_length)
        {
                // 匹配成功
                return  t_length-i;
        }
        else
        {
                // 匹配不成功
                return -1;
        }
}

void main()
{
int result;
char *a="0100000110";
char *b="10001";
result=KMP(a,b);
cout<<result;


}