数据结构--字符串匹配--模式串在主串中有多少个完全匹配的子串

模式串在主串中有多少个完全匹配的子串

ps：题目来源2025王道数据结构思维拓展

思路

KMP进行匹配
匹配成功 num+1，主串从当前匹配成功子串的起始位置的下一个位置继续匹配

if (j == t.length())
		{
    
			
			num++;
			i = i - j + 1;
			j = 0;
		}

代码

#include <iostream>
#define MAXSIZE 109
using namespace std;
int nex[MAXSIZE];
void GetNext(string s)
{
    
	int i = 0, j = -1;
	nex[0] = -1;
	while (i < s.length())
	{
    
		if (j == -1 || s[i] == s[j])
		{
    
			nex[++i] = ++j;
		}
		else
			j = nex[j];
	}
}
int KMP(string s, string t)
{
    
	int num = 0;
	int i = 0, j = 0;
	int ns = s.length(), nt = t.length(); //string.length的返回值是无符号 
	while (i < ns && j < nt)
	{
     
		if (j == -1 || s[i] == t[j])	i++, j++;
		else
			j = nex[j];
		if (j == t.length())
		{
    
			
			num++;
			i = i - j + 1;
			j = 0;
		}
	}
	return num;
}
int main()
{
    
	string s;	cin >> s;
	string t;	cin >> t;
	GetNext(t);
	
// for (int i = 0; i < t.length(); i++)
// cout << next[i] << ' ';
// cout << endl;
	cout << KMP(s, t);
}