#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
string S, T;
cin >> S >> T;
const auto GetLink = [&](string s) {
vector<int> link(s.size() + 1, 0);
for (int i = 1, j = 0; i < int(s.size()); i++) {
while (j > 0 && !(j < int(s.size()) && s[i] == s[j])) {
j = link[j];
}
if (j < int(s.size()) && s[i] == s[j]) {
j += 1;
}
link[i + 1] = j;
}
return link;
};
const auto Solve = [&]() -> array<int, 3> {
int N = S.size();
int M = T.size();
array<int, 3> ans = {0, 0, 0};
vector<int> lcs(M); // lcs[t] = longest common suffix of S[0...s], T[0...t]
for (int s = 0; s < N; s++) {
for (int t = M - 1; t >= 0; t--) {
if (S[s] == T[t]) {
lcs[t] = 1 + (t > 0 ? lcs[t - 1] : 0);
} else {
lcs[t] = 0;
}
}
vector<int> dp(M); // dp[t] = longest prefix of S[s+1...N] which is suffix of T[0...t]
string str;
for (int i = s + 1; i < N; i++) {
str.push_back(S[i]);
}
Trie trie(str);
vector<int> link = GetLink(str);
for (int t = 0, i = 0; t < M; t++) {
while (i > 0 && !(i < int(str.size()) && T[t] == str[i])) {
i = link[i];
}
if (i < int(str.size()) && T[t] == str[i]) {
i += 1;
}
dp[t] = max(dp[t], i);
}
for (int t = M - 2; t >= 0; t--) {
dp[t] = max(dp[t], dp[t + 1] - 1);
}
for (int t = 0; t < M; t++) if (lcs[t] > 0) {
int k = lcs[t] + (t < lcs[t] ? 0 : dp[t - lcs[t]]);
ans = max(ans, {k, s - lcs[t] + 1, t - k + 1});
}
}
return ans;
};
auto ans1 = Solve();
reverse(begin(T), end(T));
auto ans2 = Solve();
ans2[2] = int(T.size()) - ans2[2] - ans2[0];
auto ans = max(ans1, ans2);
cout << ans[0] << '\n' << ans[1] << ' ' << ans[2] << '\n';
return 0;
}
Compilation message
necklace.cpp: In lambda function:
necklace.cpp:47:7: error: 'Trie' was not declared in this scope
47 | Trie trie(str);
| ^~~~
