/*
بسم الله الرحمن الرحيم
Author:
(:Muhammad Aneeq:)
*/
#include <iostream>
#include <map>
#include <vector>
#include <algorithm>
using namespace std;
#define int long long
int mod=1e9+7;
int power(int x,int y)
{
int res=1;
while (y)
{
if (y&1)
res=(res*x)%mod;
x=(x*x)%mod;
y>>=1;
}
return res;
}
string x,y;
bool check(int i,int j,int k)
{
string a,b;
for (int l=i;l<i+k;l++)
a+=x[l];
for (int l=j;l<j+k;l++)
b+=y[l];
reverse(begin(a),end(a));
for (int i=0;i<b.size();i++)
{
char g=b.back();
b.pop_back();
b=g+b;
if (b==a)
return 1;
}
return 0;
}
vector<int>pr={2,3,5,7,11,13,17,19,23,29,31,37,41,43,53,59,61,67,71,73,79,83,89,97,101};
inline void solve()
{
cin>>x>>y;
int n=x.size(),m=y.size();
int hash[n+1]={};
int hash1[m+1]={};
hash[0]=hash1[0]=1;
for (int i=0;i<n;i++)
hash[i+1]=(hash[i]*pr[x[i]-'a'])%mod;
for (int i=0;i<m;i++)
hash1[i+1]=(hash1[i]*pr[y[i]-'a'])%mod;
int ans=0,l,r;
for (int k=1;k<=min(n,m);k++)
{
map<int,vector<int>>d;
for (int i=0;i<=n-k;i++)
{
int z=(hash[i+k]*power(hash[i],mod-2))%mod;
d[z].push_back(i);
}
for (int j=0;j<=m-k;j++)
{
int z=(hash1[j+k]*power(hash1[j],mod-2))%mod;
if (d.find(z)!=d.end())
{
if (ans<k)
{
if (check(d[z][0],j,k))
{
ans=k;
l=d[z][0],r=j;
}
}
}
}
}
cout<<ans<<endl;
cout<<l<<' '<<r<<endl;
}
signed main()
{
ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
solve();
}
Compilation message
necklace.cpp: In function 'bool check(long long int, long long int, long long int)':
necklace.cpp:35:17: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
35 | for (int i=0;i<b.size();i++)
| ~^~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1514 ms |
600 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
