#include <bits/stdc++.h>
using namespace std;
void fast(){ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);}
vector<int> f1(string &s, string &t){
int n=s.size(), m=t.size(), j=0;
vector<int> a(n), b(m);
for(int i=1; i<n; i++){
while(j>0 && s[i]!=s[j]) j=a[j-1];
if(s[i]==s[j]) j++;
a[i]=j;
}
j=0;
for(int i=0; i<m; i++){
while(j==n || (j>0 && s[j]!=t[i])) j=a[j-1];
if(s[j]==t[i]) j++;
b[i]=j;
}
return b;
}
vector<int> f2(string &s, string &t){
int n=s.size(), m=t.size(), j=0;
vector<int> a(n), b(m);
for(int i=1; i<n; i++){
while(j>0 && s[i]!=s[j]) j=a[j-1];
if(s[i]==s[j]) j++;
a[i]=j;
}
j=0;
for(int i=m-1; i>=0; i--){
while(j==n || (j>0 && s[j]!=t[i])) j=a[j-1];
if(s[j]==t[i]) j++;
b[i]=j;
}
return b;
}
int main(){
fast();
string s, t1, t2; cin>>s>>t1;
t2=t1; reverse(t2.begin(), t2.end());
int n=s.size(), m=t1.size();
int ki=1, ka=n, ans, j1, j2;
while(ki<=ka){
int k=(ki+ka)/2;
bool cek=false;
for(int l=0; l+k-1<n; l++){
if(cek) break;
if(k>m){
cek=true;
break;
}
string s1=s.substr(l, k);
string s2=s1; reverse(s2.begin(), s2.end());
auto val1=f1(s1, t1), val2=f2(s2, t1), val3=f1(s1, t2), val4=f2(s2, t2);
for(int i=0; i+k-1<m; i++){
if(val1[i+k-1]+val2[i]>=k){
ans=k, j1=l, j2=i;
cek=true;
break;
}
}
for(int i=0; i+k-1<m; i++){
if(val3[i+k-1]+val4[i]>=k){
ans=k, j1=l, j2=m-(i+k-1)-1;
cek=true;
break;
}
}
// if(ans==k){
// cout<<s1<<'\n';
// for(int i=0; i<m; i++) cout<<val3[i]<<' ';
// cout<<'\n';
// for(int i=0; i<m; i++) cout<<val4[i]<<' ';
// cout<<'\n';
// }
}
if(cek) ki=k+1;
else ka=k-1;
}
cout<<ans<<'\n';
cout<<j1<<' '<<j2;
}
//KMP
/*
vector<int> f(string &s){
int n=s.size(), j=0;
vector<int> v(n);
for(int i=1; i<n; i++){
while(j>0 && s[i]!=s[j]) j=v[j-1];
if(s[i]==s[j]) j++;
v[i]=j;
}
return v;
}
int main(){
fast();
string s, t; cin>>s>>t;
string temp=t+'0'+s;
auto lps=f(temp);
int ans=0;
for(auto i:lps) ans+=(i==t.size());
cout<<ans;
}*/
Compilation message
necklace.cpp: In function 'int main()':
necklace.cpp:81:20: warning: 'j2' may be used uninitialized in this function [-Wmaybe-uninitialized]
81 | cout<<j1<<' '<<j2;
| ^~
necklace.cpp:81:15: warning: 'j1' may be used uninitialized in this function [-Wmaybe-uninitialized]
81 | cout<<j1<<' '<<j2;
| ^~~
necklace.cpp:80:16: warning: 'ans' may be used uninitialized in this function [-Wmaybe-uninitialized]
80 | cout<<ans<<'\n';
| ^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
129 ms |
344 KB |
Output is correct |
| 2 |
Partially correct |
127 ms |
508 KB |
Output is partially correct |
| 3 |
Correct |
1079 ms |
508 KB |
Output is correct |
| 4 |
Correct |
664 ms |
496 KB |
Output is correct |
| 5 |
Partially correct |
416 ms |
344 KB |
Output is partially correct |
| 6 |
Partially correct |
592 ms |
344 KB |
Output is partially correct |
| 7 |
Correct |
612 ms |
500 KB |
Output is correct |
| 8 |
Correct |
895 ms |
600 KB |
Output is correct |
| 9 |
Partially correct |
651 ms |
344 KB |
Output is partially correct |
