AcWing 776. 字符串移位包含问题——KMP算法
原题链接
困难
作者:
没趣嘚紧
,
2024-02-16 11:23:43
,
所有人可见
,
阅读 34
#include <iostream>
using namespace std;
#include <vector>
vector<int> Next(string pattern) {
vector<int> next;
next.push_back(0); //next容器的首位必定为0
for (int i = 1, j = 0; i < pattern.length(); i++) {
while (j > 0 && pattern[j] != pattern[i]) {
j = next[j - 1];
}
if (pattern[i] == pattern[j]) {
j++;
}
next.push_back(j);
}
return next;
}
int main() {
string pattern, target;
cin >> target >> pattern;
if (pattern.size() > target.size()) swap(pattern, target);
target += target;
vector<int>next = Next(pattern);
for (int i = 0, j = 0; i < target.length(); i++) {
while (j > 0 && target[i] != pattern[j]) {
j = next[j - 1];
}
if (target[i] == pattern[j]) {
j++;
}
if (j == pattern.length()) {
j = next[j - 1];
cout << "true" << endl;
return 0;
}
}
cout << "false" << endl;
return 0;
}