#include <bits/stdc++.h>
#include <bits/extc++.h>
using namespace __gnu_pbds;
using namespace std;
#define ll long long
#define pll pair<ll,ll>
#define pii pair<int,int>
#define fs first
#define sc second
#define tlll tuple<ll,ll,ll>
const int mxn = 3030;
const ll mod = 712271227;
inline ll pw(ll a,ll b){
ll re = 1;
while(b){
if(b&1)re = re*a%mod;
b>>=1;
a = a*a%mod;
}
return re;
}
inline ll inv(ll k){
return pw(k,mod-2);
}
inline ll mad(ll a,ll b){
a+= b;
return a>=mod?a-mod:a;
}
inline ll mub(ll a,ll b){
return mad(a,mod-b);
}
inline pll mad(pll a,pll b){
return make_pair(mad(a.fs,b.fs),mad(a.sc,b.sc));
}
inline pll mub(pll a,pll b){
return make_pair(mub(a.fs,b.fs),mub(a.sc,b.sc));
}
const pll p = {29,31};
gp_hash_table<ll,int> mp;
string a,b;
int N,M;
const pll ip = {inv(p.fs),inv(p.sc)};
pii ans;
pll ap[mxn],bp[mxn];
string tmp;
inline bool found(string &s,int len){
pll val = make_pair(0,0);
pll h = make_pair(1,1);
for(int i = 0;i<len;i++){
val.fs = mad(val.fs,h.fs*(s[i]-'a'+1)%mod);
val.sc = mad(val.sc,h.sc*(s[i]-'a'+1)%mod);
h.fs = h.fs*p.fs%mod;
h.sc = h.sc*p.sc%mod;
}
if(mp.find(val.fs*mod+val.sc) != mp.end()){
ans.fs = mp[val.fs*mod+val.sc];
return true;
}
for(int i = len;i<s.size();i++){
val = mub(val,make_pair(s[i-len]-'a'+1,s[i-len]-'a'+1));
val.fs = mad(val.fs,h.fs*(s[i]-'a'+1)%mod);
val.sc = mad(val.sc,h.sc*(s[i]-'a'+1)%mod);
val.fs = val.fs*ip.fs%mod;
val.sc = val.sc*ip.sc%mod;
if(mp.find(val.fs*mod+val.sc) != mp.end()){
ans.fs = mp[val.fs*mod+val.sc];
return true;
}
}
return false;
}
inline bool check(int len){
if(!len){
ans.fs = ans.sc = 1;
return true;
}
mp.clear();
pll sum = ap[len];
mp[sum.fs*mod+sum.sc] = 0;
pll tp = make_pair(pw(p.fs,len),pw(p.sc,len));
for(int i = len;i<N;i++){
sum = mub(sum,make_pair(a[i-len]-'a'+1,a[i-len]-'a'+1));
sum = mad(sum,make_pair(tp.fs*(a[i]-'a'+1)%mod,tp.sc*(a[i]-'a'+1)%mod));
sum.fs = sum.fs*ip.fs%mod;
sum.sc = sum.sc*ip.sc%mod;
mp[sum.fs*mod+sum.sc] = i-len+1;
}
for(int i = 0;i+len<=M;i++){
tmp = b.substr(i,len);
tmp += tmp;
if(found(tmp,len)){
ans.sc = i;
return true;
}
reverse(tmp.begin(),tmp.end());
if(found(tmp,len)){
ans.sc = i;
return true;
}
}
return false;
}
int main(){
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
cin>>a>>b;
N = a.size(),M = b.size();
int l = 0,r = N;
pll tmp = make_pair(1,1);
for(int i = 0;i<N;i++){
ap[i+1] = ap[i];
ap[i+1].fs = mad(ap[i+1].fs,tmp.fs*(a[i]-'a'+1)%mod);
ap[i+1].sc = mad(ap[i+1].sc,tmp.sc*(a[i]-'a'+1)%mod);
tmp.fs = tmp.fs*p.fs%mod;
tmp.sc = tmp.sc*p.sc%mod;
}
tmp = make_pair(1,1);
for(int i = 0;i<M;i++){
bp[i+1] = bp[i];
bp[i+1].fs = mad(bp[i+1].fs,tmp.fs*(b[i]-'a'+1)%mod);
bp[i+1].sc = mad(bp[i+1].sc,tmp.sc*(b[i]-'a'+1)%mod);
tmp.fs = tmp.fs*p.fs%mod;
tmp.sc = tmp.sc*p.sc%mod;
}
while(l != r){
int mid = (l+r+1)>>1;
if(check(mid))l = mid;
else r = mid-1;
}
check(l);
cout<<l<<'\n'<<ans.fs<<' '<<ans.sc;
}
Compilation message
necklace.cpp: In function 'bool found(std::string&, int)':
necklace.cpp:65:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
65 | for(int i = len;i<s.size();i++){
| ~^~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
259 ms |
600 KB |
Output is correct |
| 2 |
Partially correct |
424 ms |
604 KB |
Output is partially correct |
| 3 |
Correct |
539 ms |
960 KB |
Output is correct |
| 4 |
Partially correct |
557 ms |
1092 KB |
Output is partially correct |
| 5 |
Partially correct |
387 ms |
932 KB |
Output is partially correct |
| 6 |
Partially correct |
322 ms |
932 KB |
Output is partially correct |
| 7 |
Correct |
222 ms |
600 KB |
Output is correct |
| 8 |
Correct |
874 ms |
928 KB |
Output is correct |
| 9 |
Partially correct |
452 ms |
940 KB |
Output is partially correct |
