#pragma GCC optimize("Ofast, no-stack-protector, unroll-loops")
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int mod=1e9+7;
int LN=19;
int n;int m;
int ar[6010];int br[6010];int rb[6010];
void init(){
string s;
cin>>s;
n=s.size();
s="*"+s;
for(int i=1;i<=n;i++){
ar[i]=s[i]-'a'+1;
ar[i]=ar[i]*(ar[i]+7);
// ar[i]=ar[i]*(ar[i]+3);
// ar[i+n]=ar[i];
}
cin>>s;
m=s.size();
s="*"+s;
for(int i=1;i<=m;i++){
br[i]=s[i]-'a'+1;
br[i]=br[i]*(br[i]+7);
// br[i]=br[i]*(br[i]+3);
//br[i+m]=br[i];
}
for(int i=1;i<=m;i++){
rb[i]=br[i];
}
reverse(rb+1,rb+m+1);
}
int psa[200][3010];int psb[200][3010];
int pssa[200][3010];int pssb[200][3010];
int pxa[200][3010];int pxb[200][3010];
int psrb[200][3010];
int pssrb[200][3010];
int pxrb[200][3010];
int pxxa[200][3010];
int pxxb[200][3010];
int pxxrb[200][3010];
void precalc(int len){
for(int i=1;i+len-1<=n;i++){
int v=ar[i];
for(int j=2;j<=len;j++){
v=v*27+ar[i+j-1];
v%=mod;
}
psa[len][i]=(psa[len][i-1]+v)%mod;
pssa[len][i]=(pssa[len][i-1]+v*v)%mod;
pxa[len][i]=pxa[len][i-1]^v;
pxxa[len][i]=pxxa[len][i-1]^((v*v)%mod);
}
for(int i=1;i+len-1<=m;i++){
int v=br[i];
for(int j=2;j<=len;j++){
v=v*27+br[i+j-1];
v%=mod;
}
psb[len][i]=(psb[len][i-1]+v)%mod;
pssb[len][i]=(pssb[len][i-1]+v*v)%mod;
pxb[len][i]=pxb[len][i-1]^v;
pxxb[len][i]=pxxb[len][i-1]^((v*v)%mod);
}
for(int i=1;i+len-1<=m;i++){
int v=rb[i];
for(int j=2;j<=len;j++){
v=v*27+rb[i+j-1];
v%=mod;
}
psrb[len][i]=(psrb[len][i-1]+v)%mod;
pssrb[len][i]=(pssrb[len][i-1]+v*v)%mod;
pxrb[len][i]=pxrb[len][i-1]^v;
pxxrb[len][i]=pxxrb[len][i-1]^((v*v)%mod);
}
}
int cyc(int l,int r,int st,int len){
int ret=ar[st];
for(int i=2;i<=len;i++){
st++;
if(st==r+1){st=l;}
ret=ret*27+ar[st];
ret%=mod;
}
return ret;
}
int cycb(int l,int r,int st,int len){
int ret=br[st];
for(int i=2;i<=len;i++){
st++;
if(st==r+1){st=l;}
ret=ret*27+br[st];
ret%=mod;
}
return ret;
}
int cycrb(int l,int r,int st,int len){
int ret=rb[st];
for(int i=2;i<=len;i++){
st++;
if(st==r+1){st=l;}
ret=ret*27+rb[st];
ret%=mod;
}
return ret;
}
int ansa;int ansb;
int ok(int mi){
map<vector<array<int,4>>,int>mp;
for(int i=1;i<=n-mi+1;i++){
vector<array<int,4>>vc;
int l=i;int r=i+mi-1;
for(int len=1;len<=LN;len++){
array<int,4>tar;
tar[0]=0;tar[1]=0;tar[2]=0;tar[3]=0;
if(r-len+1>=l){
tar[0]=(psa[len][r-len+1]-psa[len][l-1]+mod)%mod;
tar[1]=(pssa[len][r-len+1]-pssa[len][l-1]+mod)%mod;
tar[2]=pxa[len][r-len+1]^pxa[len][l-1];
tar[3]=pxxa[len][r-len+1]^pxxa[len][l-1];
}
for(int j=max(l,r-len+1+1);j<=r;j++){
int v=cyc(l,r,j,len);
tar[0]=(tar[0]+v)%mod;
tar[1]=(tar[1]+v*v)%mod;
tar[2]=tar[2]^v;
tar[3]=tar[3]^((v*v)%mod);
}
// cout<<i<<" "<<tar[0]<<" "<<tar[1]<<" "<<tar[2]<<endl;
vc.push_back(tar);
}
//sort(vc.begin(),vc.end());
mp[vc]=i;
}
for(int i=1;i<=m-mi+1;i++){
vector<array<int,4>>vc;
int l=i;int r=i+mi-1;
for(int len=1;len<=LN;len++){
array<int,4>tar;
tar[0]=0;tar[1]=0;tar[2]=0;tar[3]=0;
if(r-len+1>=l){
tar[0]=(psb[len][r-len+1]-psb[len][l-1]+mod)%mod;
tar[1]=(pssb[len][r-len+1]-pssb[len][l-1]+mod)%mod;
tar[2]=pxb[len][r-len+1]^pxb[len][l-1];
tar[3]=pxxb[len][r-len+1]^pxxb[len][l-1];
}
for(int j=max(l,r-len+1+1);j<=r;j++){
int v=cycb(l,r,j,len);
tar[0]=(tar[0]+v)%mod;
tar[1]=(tar[1]+v*v)%mod;
tar[2]=tar[2]^v;
tar[3]=tar[3]^( (v*v)%mod );
}
vc.push_back(tar);
}
//sort(vc.begin(),vc.end());
if(mp[vc]>=1){
ansa=mp[vc];
ansb=i;
return 1;
}
}
for(int i=1;i<=m-mi+1;i++){
vector<array<int,4>>vc;
int l=i;int r=i+mi-1;
for(int len=1;len<=LN;len++){
array<int,4>tar;
tar[0]=0;tar[1]=0;tar[2]=0;tar[3]=0;
if(r-len+1>=l){
tar[0]=(psrb[len][r-len+1]-psrb[len][l-1]+mod)%mod;
tar[1]=(pssrb[len][r-len+1]-pssrb[len][l-1]+mod)%mod;
tar[2]=pxrb[len][r-len+1]^pxrb[len][l-1];
tar[3]=pxxrb[len][r-len+1]^pxxrb[len][l-1];
}
for(int j=max(l,r-len+1+1);j<=r;j++){
int v=cycrb(l,r,j,len);
tar[0]=(tar[0]+v)%mod;
tar[1]=(tar[1]+v*v)%mod;
tar[2]=tar[2]^v;
tar[3]=tar[3]^( (v*v)%mod );
}
vc.push_back(tar);
}
//sort(vc.begin(),vc.end());
if(mp[vc]>=1){
ansa=mp[vc];
ansb=m-(i+mi-1)+1;
return 1;
}
}
return 0;
}
signed main()
{
init();
for(int i=1;i<=LN;i++){
precalc(i);
}/*
for(int i=1;i<=n;i++){
cout<<ar[i]<<" ";
}cout<<endl;
*/
// ok(1);return 0;
int l=0;int r=n;
for(int i=1;i<=n;i++){
if(ok(i)){l=i;}//else{break; }
}
cout<<l<<endl;
ok(l);
cout<<ansa-1<<" "<<ansb-1<<endl;
}
Compilation message
necklace.cpp:1:63: warning: bad option '-f no-stack-protector' to pragma 'optimize' [-Wpragmas]
1 | #pragma GCC optimize("Ofast, no-stack-protector, unroll-loops")
| ^
necklace.cpp:1:63: warning: bad option '-f unroll-loops' to pragma 'optimize' [-Wpragmas]
necklace.cpp:9:11: warning: bad option '-f no-stack-protector' to attribute 'optimize' [-Wattributes]
9 | void init(){
| ^
necklace.cpp:9:11: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
necklace.cpp:45:21: warning: bad option '-f no-stack-protector' to attribute 'optimize' [-Wattributes]
45 | void precalc(int len){
| ^
necklace.cpp:45:21: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
necklace.cpp:81:35: warning: bad option '-f no-stack-protector' to attribute 'optimize' [-Wattributes]
81 | int cyc(int l,int r,int st,int len){
| ^
necklace.cpp:81:35: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
necklace.cpp:91:36: warning: bad option '-f no-stack-protector' to attribute 'optimize' [-Wattributes]
91 | int cycb(int l,int r,int st,int len){
| ^
necklace.cpp:91:36: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
necklace.cpp:101:37: warning: bad option '-f no-stack-protector' to attribute 'optimize' [-Wattributes]
101 | int cycrb(int l,int r,int st,int len){
| ^
necklace.cpp:101:37: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
necklace.cpp:113:14: warning: bad option '-f no-stack-protector' to attribute 'optimize' [-Wattributes]
113 | int ok(int mi){
| ^
necklace.cpp:113:14: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
necklace.cpp:199:13: warning: bad option '-f no-stack-protector' to attribute 'optimize' [-Wattributes]
199 | signed main()
| ^
necklace.cpp:199:13: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
necklace.cpp: In function 'int main()':
necklace.cpp:211:17: warning: unused variable 'r' [-Wunused-variable]
211 | int l=0;int r=n;
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
55 ms |
1364 KB |
Output is correct |
| 2 |
Correct |
51 ms |
1452 KB |
Output is correct |
| 3 |
Correct |
73 ms |
1456 KB |
Output is correct |
| 4 |
Correct |
78 ms |
1464 KB |
Output is correct |
| 5 |
Correct |
114 ms |
1620 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
55 ms |
1364 KB |
Output is correct |
| 2 |
Correct |
51 ms |
1452 KB |
Output is correct |
| 3 |
Correct |
73 ms |
1456 KB |
Output is correct |
| 4 |
Correct |
78 ms |
1464 KB |
Output is correct |
| 5 |
Correct |
114 ms |
1620 KB |
Output is correct |
| 6 |
Correct |
912 ms |
2072 KB |
Output is correct |
| 7 |
Correct |
923 ms |
2168 KB |
Output is correct |
| 8 |
Incorrect |
1266 ms |
2048 KB |
Output isn't correct |
| 9 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
55 ms |
1364 KB |
Output is correct |
| 2 |
Correct |
51 ms |
1452 KB |
Output is correct |
| 3 |
Correct |
73 ms |
1456 KB |
Output is correct |
| 4 |
Correct |
78 ms |
1464 KB |
Output is correct |
| 5 |
Correct |
114 ms |
1620 KB |
Output is correct |
| 6 |
Correct |
912 ms |
2072 KB |
Output is correct |
| 7 |
Correct |
923 ms |
2168 KB |
Output is correct |
| 8 |
Incorrect |
1266 ms |
2048 KB |
Output isn't correct |
| 9 |
Halted |
0 ms |
0 KB |
- |
