实现字符串单模式匹配算法.cpp

来自「这个是我的大学作业哦 里面有些很经典的代码 出自清华大学的数据结构课本」· C++ 代码 · 共 72 行

#include <iostream>
#include <cstring>
using namespace std;
//*********************
int* getnext(char* p) {

	const int size = strlen(p);
	int* next = new int[size];
	next[0] = -1;
	for(int march = 1; march < size; march++)
	{
		int max_sub = next[march - 1];

		while(p[max_sub + 1] != p[march] && max_sub >= 0)
			max_sub = next[max_sub];
//*
		if(p[max_sub + 1] == p[march])
			next[march] = max_sub + 1;
		else next[march] = -1;
	}
	return next;
}
//-----------------------------------------------------------------
int kmp(char* t, char* p) {
	int t_size = strlen(t);
	int p_size = strlen(p);

	int* a = getnext(p); 

	for(size_t i = 0, j = 0; i < p_size && j < t_size;)
	{
		if( p[i] == t[j] )
		{
			i++;
			j++;
		}
		else
			if(i == 0)  j++;
		else
			i = a[i-1] + 1;
	}
		
	if(i < p_size) 
		{
			delete a;
			return -1;
		}
		else
		{
			delete a;
			return j - p_size + 1; 
		}
}
//************************************ 
int main() {
	char* t = "abcadbdbabdfrebs";
	char* p = "abd";
	cout << kmp(t, p) << endl;
}