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

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

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

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include <unordered_set>
#include
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;
}

uncategorized > 2019Icpc选拔赛
[徐州网络赛][KMP]D-Carneginon
https://47.97.0.163/2019/09/19/徐州网络赛kmpd-carneginon/
作者
John Doe
发布于
2019年9月19日
许可协议