#include <algorithm>
#include <iostream>
#include <map>
#include <queue>
using namespace std;
#define ll long long
ll powmod(ll a,ll b,ll c)
{
if(b==1)
return a;
if(b==0)
return 1;
ll h=powmod(a,b/2,c);
h=(h*h)%c;
if(b&1)
h=(h*a)%c;
return h;
}
struct Hashing
{
ll hash=0;
deque<char> cp;
ll l=0;
ll base;
ll mod;
ll inv;
Hashing(ll a=717,ll b=1e9+7){
base=a;
mod=b;
inv=powmod(base,mod-2,mod);
}
void push_back(char c)
{
hash=(((hash*base)%mod)+(c-'a'))%mod;
cp.push_back(c);
l++;
}
void push_front(char c)
{
hash=(((powmod(base,l,mod)*(c-'a'))%mod)+hash)%mod;
cp.push_front(c);
l++;
}
void pop_back()
{
hash=(hash+mod-(cp.back()-'a'))%mod;
hash=(hash*inv)%mod;
cp.pop_back();
l--;
}
char front()
{
return cp.front();
}
char back()
{
return cp.back();
}
int size()
{
return cp.size();
}
void pop_front()
{
l--;
hash=(hash-((powmod(base,l,mod)*(cp.front()-'a'+1))%mod)+mod)%mod;
cp.pop_front();
}
ll hash_value()
{
return ((hash%mod)+mod)%mod;
}
};
int main()
{
string a,b;
cin>>a>>b;
map<pair<ll,ll>,int> fpp;
int n=a.size();
for(int i=0;i<n;i++)
{
Hashing lp;
Hashing lpp(919,1e9+9);
Hashing lp1;
Hashing lpp1(919,1e9+9);
for(int j=i;j<n;j++)
{
lp.push_back(a[j]);
lpp.push_back(a[j]);
lp1.push_front(a[j]);
lpp1.push_front(a[j]);
for(int l=0;l<(j-i+1);l++)
{
fpp[{lp.hash_value(),lpp.hash_value()}]=i;
fpp[{lp1.hash_value(),lpp1.hash_value()}]=i;
char f=lp.front();
lp.pop_front();
lp.push_back(f);
f=lpp.front();
lpp.pop_front();
lpp.push_back(f);
f=lp1.front();
lp1.pop_front();
lp1.push_back(f);
f=lpp1.front();
lpp1.pop_front();
lpp1.push_back(f);
}
}
}
int m=b.size();
int mx=0;
int ip=-1;
int jp=-1;
for(int i=0;i<m;i++)
{
Hashing tp;
Hashing tpp;
for(int j=i;j<m;j++)
{
tp.push_back(b[j]);
tpp.push_back(b[j]);
if(fpp.find({tp.hash_value(),tpp.hash_value()})!=fpp.end())
{
if((int)(tp.size())>mx)
{
mx=(int)(tp.size());
ip=fpp[{tp.hash_value(),tpp.hash_value()}];
jp=i;
}
}
}
}
cout<<mx<<endl;
cout<<ip<<' '<<jp<<endl;
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
136 ms |
11092 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
136 ms |
11092 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
136 ms |
11092 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
