#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("sse,sse2,ssse3,sse3,sse4,popcnt,avx,mmx,abm,tune=native")
#include <bits/stdc++.h>
#define DEBUG 1
using namespace std;
namespace output{
void __(short x){cout<<x;}
void __(unsigned x){cout<<x;}
void __(int x){cout<<x;}
void __(long long x){cout<<x;}
void __(unsigned long long x){cout<<x;}
void __(double x){cout<<x;}
void __(long double x){cout<<x;}
void __(char x){cout<<x;}
void __(const char*x){cout<<x;}
void __(const string&x){cout<<x;}
void __(bool x){cout<<(x?"true":"false");}
template<class S,class T>
void __(const pair<S,T>&x){__(DEBUG?"(":""),__(x.first),__(DEBUG?", ":" "),__(x.second),__(DEBUG?")":"");}
template<class T>
void __(const vector<T>&x){__(DEBUG?"{":"");bool _=0;for(const auto&v:x)__(_?DEBUG?", ":" ":""),__(v),_=1;__(DEBUG?"}":"");}
template<class T>
void __(const set<T>&x){__(DEBUG?"{":"");bool _=0;for(const auto&v:x)__(_?DEBUG?", ":" ":""),__(v),_=1;__(DEBUG?"}":"");}
template<class T>
void __(const multiset<T>&x){__(DEBUG?"{":"");bool _=0;for(const auto&v:x)__(_?DEBUG?", ":" ":""),__(v),_=1;__(DEBUG?"}":"");}
template<class S,class T>
void __(const map<S,T>&x){__(DEBUG?"{":"");bool _=0;for(const auto&v:x)__(_?DEBUG?", ":" ":""),__(v),_=1;__(DEBUG?"}":"");}
void pr(){cout<<"\n";}
template<class S,class... T>
void pr(const S&a,const T&...b){__(a);if(sizeof...(b))__(' ');pr(b...);}
}
using namespace output;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<int,char> pic;
typedef pair<double,double> pdd;
typedef pair<ld,ld> pld;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef pair<int,vi> piv;
#define pb push_back
#define fox(i,x,y) for(int i=(x);i<=(y);i++)
#define foxr(i,x,y) for(int i=(y);i>=(x);i--)
const int MN = 3003;
string s, t;
int n, m, i, hsh[2][MN], pw[MN]={1}, pre[MN], suf[MN], st[MN], len[MN], lo, hi, lim1, lim2, ans, sw, fl, ree, k, sh, mid;
inline int gethsh(int id,int x,int y){return hsh[id][y]-hsh[id][x-1]*pw[y-x+1];}
pii sna; queue<pii> hm;
void solve(int init=0){
for(int i=1;i<=m;i++)
hsh[1][i]=hsh[1][i-1]*133+t[i-1]-'a'+1;
k = min(m,lim2);
for(int i=n;i>=1;i--){
if(s[i-1]!=t[m-1]){
suf[i]=0;
continue;
}
//if(init||i==n){
hi=min(i,k);
lo=min(hi,max(0,suf[i+1]-1));
while(lo<hi){
mid = (lo+hi)/2;
if(gethsh(0,i-mid,i)==gethsh(1,m-mid,m)) lo=mid+1;
else hi=mid;
}
suf[i]=lo;
/*}
else{
suf[i]=max(0,suf[i+1]-1);
}*/
}
while(hm.size()) hm.pop();
for(int i=n;i>=1;i--){
if(suf[i]) hm.push({suf[i],i});
while(hm.size()){
if(hm.front().second-hm.front().first+1>i) hm.pop();
else break;
}
if(hm.size()){
st[i] = lim2-hm.front().first;
len[i] = hm.front().second-i+1;
}
else len[i] = 0, st[i] = lim2;
}
k = min(m,lim1);
for(int i=1;i<=n;i++){
if(s[i-1]!=t[0]){
pre[i]=0;
continue;
}
hi=min(n-i+1,k);
lo=min(hi,max(pre[i-1]-1,0));
while(lo<hi){
mid = (lo+hi)/2;
if(gethsh(0,i,i+mid)==gethsh(1,1,1+mid)) lo=mid+1;
else hi=mid;
}
pre[i]=lo;
}
while(hm.size()) hm.pop();
for(int i=1;i<=n;i++){
if(pre[i]) hm.push({pre[i],i});
while(hm.size()){
if(hm.front().second+hm.front().first-1<i) hm.pop();
else break;
}
if(hm.size()){
len[i] = i-hm.front().second+1;
if(len[i]+len[i+1]>ans){
ans = len[i]+len[i+1];
if(sw) sna = {n-(i+len[i+1]), st[i+1]};
else sna = {hm.front().second-1, st[i+1]};
}
}
}
}
int main(){
cin >> s >> t;
n = s.size(), m = t.size();
for(i=1;i<MN;i++)
pw[i]=133*pw[i-1];
for(i=1;i<=n;i++)
hsh[0][i]=hsh[0][i-1]*133+s[i-1]-'a'+1;
lim1 = 0; lim2 = m;
solve(1);
for(i=1;i<=m;i++){
lim1++; lim2--;
char ch = t.back(); t.erase(t.end()-1);
t.insert(t.begin(),ch);
solve();
}
for(i=0;i<s.size()/2;i++)
swap(s[i],s[s.size()-i-1]);
for(i=1;i<=n;i++)
hsh[0][i]=hsh[0][i-1]*133+s[i-1]-'a'+1;
lim1 = 0; lim2 = m; sw = 1;
solve(1);
for(i=1;i<=m;i++){
lim1++; lim2--;
char ch = t.back(); t.erase(t.end()-1);
t.insert(t.begin(),ch);
solve();
}
printf("%d\n%d %d\n",ans,sna.first,sna.second);
return 0;
}
Compilation message
necklace.cpp: In function 'int main()':
necklace.cpp:142:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(i=0;i<s.size()/2;i++)
~^~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
372 KB |
Output is correct |
| 2 |
Correct |
5 ms |
376 KB |
Output is correct |
| 3 |
Correct |
6 ms |
376 KB |
Output is correct |
| 4 |
Correct |
6 ms |
376 KB |
Output is correct |
| 5 |
Correct |
5 ms |
376 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
372 KB |
Output is correct |
| 2 |
Correct |
5 ms |
376 KB |
Output is correct |
| 3 |
Correct |
6 ms |
376 KB |
Output is correct |
| 4 |
Correct |
6 ms |
376 KB |
Output is correct |
| 5 |
Correct |
5 ms |
376 KB |
Output is correct |
| 6 |
Correct |
33 ms |
376 KB |
Output is correct |
| 7 |
Correct |
20 ms |
376 KB |
Output is correct |
| 8 |
Correct |
35 ms |
376 KB |
Output is correct |
| 9 |
Correct |
24 ms |
376 KB |
Output is correct |
| 10 |
Correct |
10 ms |
376 KB |
Output is correct |
| 11 |
Correct |
10 ms |
376 KB |
Output is correct |
| 12 |
Correct |
25 ms |
376 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
372 KB |
Output is correct |
| 2 |
Correct |
5 ms |
376 KB |
Output is correct |
| 3 |
Correct |
6 ms |
376 KB |
Output is correct |
| 4 |
Correct |
6 ms |
376 KB |
Output is correct |
| 5 |
Correct |
5 ms |
376 KB |
Output is correct |
| 6 |
Correct |
33 ms |
376 KB |
Output is correct |
| 7 |
Correct |
20 ms |
376 KB |
Output is correct |
| 8 |
Correct |
35 ms |
376 KB |
Output is correct |
| 9 |
Correct |
24 ms |
376 KB |
Output is correct |
| 10 |
Correct |
10 ms |
376 KB |
Output is correct |
| 11 |
Correct |
10 ms |
376 KB |
Output is correct |
| 12 |
Correct |
25 ms |
376 KB |
Output is correct |
| 13 |
Execution timed out |
1596 ms |
376 KB |
Time limit exceeded |
| 14 |
Halted |
0 ms |
0 KB |
- |
