C++KMP字符串匹配

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了C++KMP字符串匹配，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1346字，纯文字阅读大概需要2分钟。

内容图文

#include<iostream>
#define defaultsize 30
using namespace std;


typedef struct {
	char*ch;
	int maxsize;
	int n;
}HString;

void HStringInit(HString&S, int n=defaultsize)
{
	if (n < defaultsize)
		n = defaultsize;
	S.ch = new char[n];
	S.maxsize = n;
	S.n = n;
}

void CreateHString(HString&S, char c[])
{
	int i = 0;
	while (c[i] != '\0'&&i<S.maxsize)
	{
		S.ch[i] = c[i];
		i++;
	}
	if (c[i] != '\0')
		cout << "超出存储空间" << endl;
	else
		S.n = i;
}


void Print(HString&S)
{
	for (int i = 0;i < S.n;i++)
		cout << S.ch[i] << " ";
}

int find(const HString&T, const HString&P)
{
	for (int i = 0;i < T.n - P.n+1;i++)
	{
		int j = 0;
		for (j = 0;j < P.n;j++)
		{
			if (P.ch[j] != T.ch[j + i])
				break;
		}
		if (j == P.n&&P.ch[j] == T.ch[i+j])
		{
			return i;
		}

	}
}

void GetNext(HString&S, int next[])
{
	int j = 0, k = -1;next[j] = k;
	while(j<S.n)
	{
		while (k >= 0 && S.ch[k] != S.ch[j])k = next[k];
		j++;k++;
		if (S.ch[k] == S.ch[j])next[j] = next[k];
		else next[j] = k;
	}
}

int FastFind(HString&T, HString&P,int next[])
{
	int i = 0, j = 0;
	while (i < T.n&&j < P.n)
	{
		if (j == -1 || T.ch[i] == P.ch[j]) { i++;j++; }
		else j = next[j];
	}
	if (j < P.n)return -1;
	else return i - P.n;
}


int main()
{
	HString S1;
	HString S2;
	HStringInit(S1);
	HStringInit(S2);
	char c1[] = "dad";
	char c2[] = "aadad";
	CreateHString(S1, c1);
	CreateHString(S2, c2);
	Print(S1);
	Print(S2);
	int next[sizeof(c1) / sizeof(char)];
	GetNext(S1, next);
	cout << FastFind(S2, S1, next);
	system("pause");
}

内容总结

以上是互联网集市为您收集整理的C++KMP字符串匹配全部内容，希望文章能够帮你解决C++KMP字符串匹配所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端