#include<bits/stdc++.h>
using namespace std;
#define pb push_back
template<typename T> bool chkmin(T &a, T b){return b < a ? a = b, 1 : 0;}
template<typename T> bool chkmax(T &a, T b){return b > a ? a = b, 1 : 0;}
vector<int> kmp(string s, string t){
vector<int> nxt(s.size(), 0), mat(t.size(), 0);
if(s.size() == 0) return mat; // empty pattern
nxt[0] = 0;
for(int i = 1; i < (int)s.size(); i++){
int len = nxt[i - 1];
while(len > 0 && s[len] != s[i])
len = nxt[len - 1];
if(s[i] == s[len]) len++;
nxt[i] = len;
}
int len = 0;
for(int i = 0; i < (int)t.size(); i++){
while(len > 0 && t[i] != s[len])
len = nxt[len - 1];
if(t[i] == s[len]) len++;
mat[i] = len;
if(len == (int)s.size())
len = nxt[len - 1];
}
return mat;
}
int n, m;
string a, b, br;
int main(){
cin >> a >> b;
n = (int)a.size(); m = (int)b.size();
br = b;
reverse(br.begin(), br.end());
int ans = 0, cuta, cutb;
for(int cas = 1; cas <= 2; cas++){
for(int i = 0; i < n; i++){ // reverse before i
string s1 = a.substr(i, n - i), s2 = a.substr(0, i);
vector<int> l, r;
l = kmp(s1, b);
reverse(s2.begin(), s2.end());
r = kmp(s2, br);
reverse(r.begin(), r.end());
if(chkmax(ans, r[0]))
cuta = i - r[0], cutb = (cas == 1 ? 0 : m - r[0]);
if(chkmax(ans, l[m - 1]))
cuta = i, cutb = (cas == 1 ? m - l[m - 1] : 0);
for(int j = 0; j < m - 1; j++)
if(chkmax(ans, l[j] + r[j + 1]))
cuta = i - r[j + 1], cutb = (cas == 1? j - l[j] + 1: m - j - r[j + 1] - 1);
}
swap(b, br);
}
cout << ans << endl;
cout << cuta << " " << cutb << endl;
}
Compilation message
necklace.cpp: In function 'int main()':
necklace.cpp:62:25: warning: 'cutb' may be used uninitialized in this function [-Wmaybe-uninitialized]
62 | cout << cuta << " " << cutb << endl;
| ^~~~
necklace.cpp:62:18: warning: 'cuta' may be used uninitialized in this function [-Wmaybe-uninitialized]
62 | cout << cuta << " " << cutb << endl;
| ^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
180 ms |
412 KB |
Output is correct |
| 2 |
Correct |
166 ms |
340 KB |
Output is correct |
| 3 |
Correct |
216 ms |
400 KB |
Output is correct |
| 4 |
Correct |
138 ms |
400 KB |
Output is correct |
| 5 |
Correct |
120 ms |
408 KB |
Output is correct |
| 6 |
Correct |
132 ms |
408 KB |
Output is correct |
| 7 |
Correct |
178 ms |
520 KB |
Output is correct |
| 8 |
Correct |
162 ms |
372 KB |
Output is correct |
| 9 |
Correct |
166 ms |
404 KB |
Output is correct |
