您的位置: 首页  >  文章  >  关于字符串的匹配之古典匹配到引入KMP算法

关于字符串的匹配之古典匹配到引入KMP算法

分类: 文章 • 2025-03-06 14:34:58

最近在学习数据结构，学到了串与字符串那个地方，一般都是求子串在主串中的定位问题：

古典的方法一般都是采用子串定长顺序存储结构，可以写出不依赖于其他串的操作的匹配算法，这种算法在二进制中的算术复杂度非常高，最坏情况下为O（n*m）,但是我个人觉得在不是二进制中应该也还好，这个算法的核心实际上就是将子串固定死，然后一个下标i在主串中移动，或者就是利用一下i=i-j+2,然后J又回到等于1，然后如果说最后j能够大于子串的长度，那么i减掉子串的长度就是子串此时在主串中的索引；

下面可以给出他的这个函数算法：

#include<cstdio>
#include<iostream>
#include<cstring>
#include<string>
#include<stack>
#include<cstdlib>
#include<algorithm> 
#include<sstream>

using namespace std;

void Index(string s1,string s2,int pos) {
    //1=<pos<=strlen(s1);
	int i = pos;
	int j = 1;
	while(i <= s1.length() && j <= s2.length()) {
		if(s1[i] == s2[j]) {
			++i;
			++j;
		} else {
			i = i - j + 2;
			j = 1;
		}
	}
	if(j > s2.length()) { 
		int value = i - s2.length();
		printf("第%d个位置一致:",value);
		
	} else {
		return;
	}
}


int main() {
	string s1,s2;
	printf("请输入两个字符串分别为主串和模式子串:");
	cin >> s1 >> s2;
 	Index(s1,s2,1);
	return 0; 
}

而这个时候我们可以引进来KMP算法来优化解题：

KMP算法实际上是由get_next(string s2,int next[])和Index_KMP(string s1,string s2,int pos)两个函数组成，

关于字符串的匹配之古典匹配到引入KMP算法

这个next函数实际上是对模式串进行操作，跟主串完全没有关系的，在next[1]=0,next[2]=1，这两个实际上就是固定的，我们这样在纸上是可以直接列出来的，但是怎么写出自动判断next【j】的值呢：

void get_next(string s3,int next[]) {
	//求模式串T的next函数值并且存入数组next 
	int i = 1;
	next[1] = 0;
	next[2] = 1;
	int j = 0;
	while(i < s3.length()) {
		if(j == 0 || s3[i] == s3[j]) {
			++i;
			++j;
			next[i] = j;
		} else {
			j = next[j];
		}
	}
} //get_next

然后下面给出Index_KMP算法函数：

int Index_KMP(string s1,string s2,int pos) {
	int i = pos;
	int j = 1;
	while(i <= s1.length() && j <= s2.length()) {
		if(j == 0 || s1[i] == s2[j]) {
			i++;
			j++;
		} else {
			j = get_next[j];
		}
		if(j > s2.length()) {
			return i - s2.length();
		}
	}
}

下面再以一道题目来解释吧：

串结构练习——字符串匹配

Time Limit: 1000ms   Memory limit: 65536K  有疑问？点这里^_^

题目链接：http://acm.sdut.edu.cn/sdutoj/problem.php?action=showproblem&problemid=2125

题目描述

  给定两个字符串string1和string2，判断string2是否为string1的子串。

 

输入

 输入包含多组数据，每组测试数据包含两行，第一行代表string1，第二行代表string2，string1和string2中保证不出现空格。

 

输出

 对于每组输入数据，若string2是string1的子串，则输出"YES"，否则输出"NO"。

 

示例输入

abc
a
123456
45
abc
ddd

示例输出

YES
YES
NO

代码如下所示：

#include<string.h>
#include<iostream>
using namespace std;
char S[100],T[100];
int s,t,next[100],nextval[100];
void get_next(char T[],int next[]);//对应模式匹配算法一next函数值
void get_nextval(char T[],int nextval[]);//对应模式匹配算法二nextval函数值
int Index_KMP(char S[],char T[],int pos);//模式匹配算法一
int Index_KMP2(char S[],char T[],int pos);//模式匹配算法二
int main()
{
    while(cin>>S>>T)
    {
        memset(next,0,sizeof(next));
        int i;
        s=strlen(S);
        t=strlen(T);
        for(i=s;i>=1;i--)
            S[i]=S[i-1];
        S[s+1]='\0';
        for(i=t;i>=1;i--)
            T[i]=T[i-1];
        T[t+1]='\0';
        //get_next(T,next);
        get_nextval(T,nextval);
        //int flag=Index_KMP(S,T,1);//通过这里可以验证两个算法
        int flag=Index_KMP2(S,T,1);
        //for(i=1;i<=t;i++)
          //  cout<<nextval[i]<<" ";
        //cout<<endl;
        if(flag==0)cout<<"NO"<<endl;
        else cout<<"YES"<<endl;
    }
    return 0;
}
void get_next(char T[],int next[])//对应模式匹配算法一next函数值
{
    int i=1,j=0;
    next[1]=0;
    while(i<t)
    {
        if(j==0||T[i]==T[j])
        {
            ++i;
            ++j;
            next[i]=j;
        }
        else j=next[j];
    }
}
void get_nextval(char T[],int nextval[])//对应模式匹配算法二nextval函数值
{
    int i=1,j=0;
    nextval[1]=0;
    while(i<t)
    {
        if(j==0||T[i]==T[j])
        {
            ++i;
            ++j;
            if(T[i]!=T[j])
                nextval[i]=j;
            else
                nextval[i]=nextval[j];
        }
        else
            j=nextval[j];
    }
}
int Index_KMP(char S[],char T[],int pos)//模式匹配算法一
{
    int i=pos,j=1;
    while(i<=s&&j<=t)
    {
        if(j==0||S[i]==T[j])
        {
            ++i;
            ++j;
        }
        else j=next[j];
    }
    if(j>t)return i-t;
    else return 0;
}
int Index_KMP2(char S[],char T[],int pos)//模式匹配算法二
{
    int i=pos,j=1;
    while(i<=s&&j<=t)
    {
        if(j==0||S[i]==T[j])
        {
            ++i;
            ++j;
        }
        else j=nextval[j];
    }
    if(j>t)return i-t;
    else return 0;
}

还有一道题目是南阳OJ上面的，题目的基本意思是问你在主串中，子串出现的次数：

下面是代码：

#include<cstdio>
#include<iostream>
#include<cstring>
#include<string>
#include<stack>
#include<cstdlib>

using namespace std;

int main() {
	int n;	//表示n组测试数据 
//	cin >> n;
	string s1;	//字符串s1比较短 
	string s2;
	int cnt = 0;
	int len1 = s1.length();
	int len2 = s2.length();
	cin >> n;
	while(n--) {
		cnt = 0;
		cin >> s1;
		cin >> s2;
		int ans = s2.find(s1); //在s2子串里面查找s1 
		while(1) {			//用了一个死循环加break； 
			if(s2.find(s1) != -1) {
				cnt++;
				s2[s2.find(s1)] = '3';	//这一部是关键，相当于把走过的路都做了标记 
			} else {
				break;
			}
		}
			cout << cnt << endl;
		}
}

下面的是OJ上看到的参考代码：

#include<iostream>
#include<string>
using namespace std;
int main()
{
	string s1,s2;
	int n;
	cin>>n;
	while(n--)
	{
		cin>>s1>>s2;
		unsigned int m=s2.find(s1,0);
		int num=0;
		while(m!=string::npos)
		{
			num++;
			m=s2.find(s1,m+1);
		}
		cout<<num<<endl;
	}
}

 

相关推荐