题解 | #String Matching#

String Matching

https://www.nowcoder.com/practice/00438b0bc9384ceeb65613346b42e88a

//土尔逊Torson 编写于2023/4/22
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <stdlib.h>

using namespace std;

const int MAXM = 10000;

int nextTable[MAXM];

void GetNextTable(string pattern) {
	int m = pattern.size();
	int j = 0;
	nextTable[j] = -1;
	int i = nextTable[j];
	while (j < m) {
		if (i == -1 || pattern[j] == pattern[i]) {
			i++;
			j++;
			nextTable[j] = i;
		}
		else {
			i = nextTable[i];
		}
	}
	return;
}

int KMP(string text, string pattern) {
	GetNextTable(pattern);
	int n = text.size();
	int m = pattern.size();
	int i = 0;
	int j = 0;
	int number = 0;
	while (i < n) {
		if (j == -1 || text[i] == pattern[j]) {
			i++;
			j++;
		}
		else {
			j = nextTable[j];
		}
		if (j == m) {
			number++;
			j = nextTable[j];
		}
	}
	return number;
}

int main() {
	string line;
	while (getline(cin,line)) {
		string pattern, text;
		int g = line.find(' ');
		int u = line.find('\0');
		//printf("%d %d\n", g, u);
		text = line.substr(0, g);
		pattern = line.substr(g + 1,u-g);
		//printf("%s %s\n", text.c_str(), pattern.c_str());
		printf("%d\n", KMP(text, pattern));
	}
	system("pause");
	return EXIT_SUCCESS;
}
// 64 位输出请用 printf("%lld")

全部评论

相关推荐

不愿透露姓名的神秘牛友
07-08 13:05
点赞 评论 收藏
分享
点赞 评论 收藏
分享
机械打工仔:我来告诉你原因,是因为sobb有在线简历,有些HR为了快会直接先看在线简历,初步感觉不合适就不会找你要详细的了
投了多少份简历才上岸
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务