Skip to content

kmp第一次

代码高亮加载可能需要时间,请稍微等待下

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

using namespace std;

int givenum(string a);//给出具体某个数的匹配值
int kmp(string a, string standard);// 字符匹配
int getpart(string a); //得到part数组


int part[20];//部分匹配数组

int main()
{

	memset(part, 0, sizeof(part));
	string duru;
	cin >> duru;
	cin.get();
	getpart(duru);
	string tocompare;
	getline(cin, tocompare);
	cout << (kmp(tocompare, duru)) << endl;

	return 0;
}



int getpart(string a)
{
	int len = a.length();
	string temp;
	for (int i = 0; i < len; i++)
	{
		temp += a[i];
		part[i] = givenum(temp);
	}
	return 0;
}

int kmp(string a, string standard)
{
	int alen = a.length();
	int slen = standard.length();
	int flag = 0;
	int aloca = 0, sloca = 0;
	while (aloca != alen)
	{
		if (a[aloca] == standard[sloca])
		{
			if (sloca == slen - 1)
			{
				flag++;
				aloca++;
				sloca = 0;
			}
			else
			{
				aloca++;
				sloca++;
			}
		}
		else
		{
			if (sloca == 0)
			{
				aloca++;
			}
			else
			{
				sloca = part[sloca - 1];
			}
		}
	}
	return flag;
}


int givenum(string a)
{
	int len = a.length();
	int maxit = 0;
	for (int i = 0; i < len; i++)
	{
		int cnt = 0;
		for (int j = 0; j < i; j++)
		{
			if (a[j] == a[j + len - i])
				cnt++;
			else
			{
				cnt = 0;
				break;
			}
		}
		if (cnt > maxit)
			maxit = cnt;
	}
	return maxit;
}