文章

68

粉丝

691

获赞

24

访问

547.9k

头像
KMP
P1207
发布于2020年5月20日 11:56
阅读数 6.8k

#include<iostream>
#include<cstdio>
#include<string>
#include<string.h>
#include<algorithm>
#include<vector>
#include<map>
#include<queue>
using namespace std;

#define ll int
#define inf 0x3f3f3f3f
#define MAXN 205
#define vec vector<ll>

int next_[MAXN];
string s, t = "good morning";

void getNext() {
	next_[0] = -1;
	int i = 0, j = -1;
	while (i < t.size()) {
		if (j == -1 || t[i] == t[j]) {
			if (t[++j] == t[++i])
				next_[i] = next_[j];
			else next_[i] = j;
		}
		else
			j = next_[j];
	}
}

int cal() {
	int i = 0, j = 0, cnt = 0;
	while (i < s.length()) {
		if (j == -1 || s[i] == t[j]) { i++, j++; }
		else j = next_[j];
		if (j == t.size())
			cnt++;
	}
	return cnt;
}

int main() {
	getNext();
	while (getline(cin,s)) {
		cout << cal() << endl;
	}
}

 

登录查看完整内容


登录后发布评论

暂无评论,来抢沙发