[徐州网络赛][KMP]D-Carneginon

发布于 2019-09-19  414 次阅读


https://nanti.jisuanke.com/t/41386

给你一个字符串 再给你n个字符串 查询是否是字串 一道裸的KMP 用了Kuangbin的板子 很基础

#include<algorithm>
#include<iostream>
#include<vector>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<string>
#include<ctime>
#include<map>
#include<stack>
#include<queue>
#include<set>
#include<cstring>
#include <unordered_set>
#include <bitset>
using namespace std;
const int maxn = 1e5 + 5;
string t;
string s;
int nxt[maxn];
void prekmp(string x) {
	memset(nxt, 0, sizeof(nxt));
	int i, j;
	j = nxt[0] = -1;
	i = 0;
	int m = x.length();
	while (i < m) {
		while (-1 != j && x[i] != x[j])j = nxt[j];
		nxt[++i] = ++j;
	}
}
int kmp(string x, string y) {//x是模式串 y是主串
	int i, j;
	int ans=0;
	prekmp(x);
	int m = x.length();
	int n = y.length();
	i = j = 0;
	while (i < n) {
		while (-1 != j && y[i] != x[j]) j = nxt[j];
		i++; j++;
		if (j >= m) {
			ans = 1;
			break;
		}
	}
	return ans;
}
int main() {
	cin >> t;
	int q;
	cin >> q;
	while (q--) {
		cin >> s;
		if (t.length() > s.length()) {
			if (kmp(s, t)) cout << "my child!\n";
			else cout << "oh, child!\n";
		}
		else if (t.length() < s.length()) {
			if (kmp(t, s)) cout << "my teacher!\n";
			else cout << "senior!\n";
		}
		else {
			if (s == t) cout << "jntm!\n";
			else cout << "friend!\n";
		}
	}
	return 0;
}

愿风指引你的道路,愿你的刀刃永远锋利。