72 lines
1.9 KiB
C++
72 lines
1.9 KiB
C++
#include <iostream>
|
||
#include <string>
|
||
#include <vector>
|
||
using namespace std;
|
||
vector<int> build_next(const string& p) {
|
||
int n = p.size(); // 模式串长度
|
||
vector<int> nxt(n, 0); // 存放 next 数组，初始化全 0
|
||
|
||
for (int i = 1, j = 0; i < n; i++) {
|
||
// --- step1: 如果当前字符不匹配，回退 j ---
|
||
while (j > 0 && p[i] != p[j])
|
||
j = nxt[j - 1]; // j 回退到上一个最长前后缀的长度，采用动态规划思想
|
||
|
||
// --- step2: 如果匹配成功，j 前进 ---
|
||
if (p[i] == p[j])
|
||
j++;
|
||
|
||
// --- step3: 记录当前前缀的 next 值 ---
|
||
nxt[i] = j; // 表示 p[0..i] 的最长公共前后缀长度
|
||
}
|
||
|
||
return nxt;
|
||
}
|
||
|
||
|
||
vector<int> next_arr(const string& x) {
|
||
int n = x.size();
|
||
vector<int> tmp(n, 0);
|
||
|
||
for (int i = 0; i < n; i++) {
|
||
int j = 0;
|
||
for (int len = i; len > 0; len--) {
|
||
if (x.substr(0, len) == x.substr(i - len + 1, len)) {
|
||
j = len;
|
||
break;
|
||
}
|
||
}
|
||
tmp[i] = j;
|
||
}
|
||
return tmp;
|
||
}
|
||
|
||
|
||
int main(){
|
||
string mod, input;
|
||
cin >> input >> mod;
|
||
vector<int> next = build_next(mod);
|
||
int n = mod.size();
|
||
int pi = 0, pm = 0;
|
||
cout << next[n / 4] << " " << next[n / 2] << " " << next[3 * n / 4] << endl;
|
||
while (pi < input.size()) {
|
||
if (input[pi] == mod[pm]) {
|
||
pi++;
|
||
pm++;
|
||
if (pm == mod.size()) {
|
||
cout << pi - pm << " "; // 匹配位置（起始下标）
|
||
return 0;
|
||
pm = next[pm - 1]; // 回退
|
||
}
|
||
} else {
|
||
if (pm > 0)
|
||
pm = next[pm - 1]; // 回退
|
||
else
|
||
pi++;
|
||
}
|
||
}
|
||
cout << -1 << endl;
|
||
return 0;
|
||
}
|
||
|
||
qwerababcabcabcabcdaabcabhlk
|