#include <bits/stdc++.h>
using namespace std;
#define int long long
int h=37, mod=1e9+7;
int mul(int x, int y)
{
return (x*y)%mod;
}
int sum(int x, int y)
{
return((x+y)%mod+mod)%mod;
}
int poww(int a, int b)
{
if(b==0) return 1;
int tmp=poww(a, b/2);
if(b%2==0) return mul(tmp, tmp);
return mul(tmp, mul(tmp, a));
}
int inv(int a)
{
return (poww(a, mod-2));
}
int32_t main()
{
ios_base::sync_with_stdio(false); cin.tie(0);
string s, t; cin>>s>>t;
int ss=0;
array<int, 3> aa={0, 0, 0};
int ans=0;
for(int i=1; i<min(s.size(), t.size()); i++)
{
int tmp=i;
if(tmp<=s.size()&&tmp<=t.size())
{
queue<int> q;
map<int, int> mp;
ans=0;
for(int l=0; l<s.size(); l++)
{
if(q.size()<tmp)
{
ans=sum(ans, mul((s[l]-'a'+1), poww(37, l+1)));
q.push(l);
}
else
{
ans=sum(ans, mul(-1, mul(s[q.front()]-'a'+1, poww(37, 1))));
q.pop();
ans=mul(ans, inv(37));
ans=sum(ans, mul(s[l]-'a'+1, poww(37, tmp)));
q.push(l);
}
int pf=tmp;
if(q.size()==tmp)
while(pf--)
{
q.front();
ans=sum(ans, mul(-1, mul(s[q.front()]-'a'+1, poww(37, 1))));
q.push(q.front());
ans=mul(ans, inv(37));
ans=sum(ans, mul(s[q.front()]-'a'+1, poww(37, tmp)));
mp[ans]=l-tmp+2;
q.pop();
}
}
q=queue<int>();
ans=0;
for(int l=0; l<t.size()&&aa[0]!=tmp; l++)
{
if(q.size()<tmp)
{
ans=sum(ans, mul((t[l]-'a'+1), poww(37, l+1)));
q.push(l);
}
else
{
ans=sum(ans, mul(-1, mul(t[q.front()]-'a'+1, poww(37, 1))));
q.pop();
ans=mul(ans, inv(37));
ans=sum(ans, mul(t[l]-'a'+1, poww(37, tmp)));
q.push(l);
}
if(q.size()==tmp)
{
if(mp.count(ans)>0) aa[0]=tmp, aa[1]=mp[ans]-1, aa[2]=l-tmp+1;
}
}
if(aa[0]==tmp) ss=tmp;
}
}
auto bb=aa;
aa={0, 0, 0};
ss=0, ans=0;
reverse(s.begin(), s.end());
for(int i=1; i<min(s.size(), t.size()); i++)
{
int tmp=i;
if(tmp<=s.size()&&tmp<=t.size())
{
queue<int> q;
map<int, int> mp;
ans=0;
for(int l=0; l<s.size(); l++)
{
if(q.size()<tmp)
{
ans=sum(ans, mul((s[l]-'a'+1), poww(37, l+1)));
q.push(l);
}
else
{
ans=sum(ans, mul(-1, mul(s[q.front()]-'a'+1, poww(37, 1))));
q.pop();
ans=mul(ans, inv(37));
ans=sum(ans, mul(s[l]-'a'+1, poww(37, tmp)));
q.push(l);
}
int pf=tmp;
if(q.size()==tmp)
while(pf--)
{
q.front();
ans=sum(ans, mul(-1, mul(s[q.front()]-'a'+1, poww(37, 1))));
q.push(q.front());
ans=mul(ans, inv(37));
ans=sum(ans, mul(s[q.front()]-'a'+1, poww(37, tmp)));
mp[ans]=l+1;
q.pop();
}
}
q=queue<int>();
ans=0;
for(int l=0; l<t.size()&&aa[0]!=tmp; l++)
{
if(q.size()<tmp)
{
ans=sum(ans, mul((t[l]-'a'+1), poww(37, l+1)));
q.push(l);
}
else
{
ans=sum(ans, mul(-1, mul(t[q.front()]-'a'+1, poww(37, 1))));
q.pop();
ans=mul(ans, inv(37));
ans=sum(ans, mul(t[l]-'a'+1, poww(37, tmp)));
q.push(l);
}
if(q.size()==tmp)
{
if(mp.count(ans)>0) aa[0]=tmp, aa[1]=s.size()-mp[ans], aa[2]=l-tmp+1;
}
}
if(aa[0]==tmp) ss=tmp;
}
}
aa=max(aa, bb);
cout<<aa[0]<<" \n"<<aa[1]<<" "<<aa[2];
}
Compilation message
necklace.cpp: In function 'int32_t main()':
necklace.cpp:40:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'const long unsigned int' [-Wsign-compare]
40 | for(int i=1; i<min(s.size(), t.size()); i++)
| ~^~~~~~~~~~~~~~~~~~~~~~~~
necklace.cpp:44:15: 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]
44 | if(tmp<=s.size()&&tmp<=t.size())
| ~~~^~~~~~~~~~
necklace.cpp:44:30: 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]
44 | if(tmp<=s.size()&&tmp<=t.size())
| ~~~^~~~~~~~~~
necklace.cpp:49:27: 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]
49 | for(int l=0; l<s.size(); l++)
| ~^~~~~~~~~
necklace.cpp:52:28: warning: comparison of integer expressions of different signedness: 'std::queue<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
52 | if(q.size()<tmp)
| ~~~~~~~~^~~~
necklace.cpp:66:28: warning: comparison of integer expressions of different signedness: 'std::queue<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
66 | if(q.size()==tmp)
| ~~~~~~~~^~~~~
necklace.cpp:81:27: 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]
81 | for(int l=0; l<t.size()&&aa[0]!=tmp; l++)
| ~^~~~~~~~~
necklace.cpp:83:28: warning: comparison of integer expressions of different signedness: 'std::queue<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
83 | if(q.size()<tmp)
| ~~~~~~~~^~~~
necklace.cpp:97:28: warning: comparison of integer expressions of different signedness: 'std::queue<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
97 | if(q.size()==tmp)
| ~~~~~~~~^~~~~
necklace.cpp:114:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'const long unsigned int' [-Wsign-compare]
114 | for(int i=1; i<min(s.size(), t.size()); i++)
| ~^~~~~~~~~~~~~~~~~~~~~~~~
necklace.cpp:117:15: 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]
117 | if(tmp<=s.size()&&tmp<=t.size())
| ~~~^~~~~~~~~~
necklace.cpp:117:30: 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]
117 | if(tmp<=s.size()&&tmp<=t.size())
| ~~~^~~~~~~~~~
necklace.cpp:122:27: 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]
122 | for(int l=0; l<s.size(); l++)
| ~^~~~~~~~~
necklace.cpp:125:28: warning: comparison of integer expressions of different signedness: 'std::queue<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
125 | if(q.size()<tmp)
| ~~~~~~~~^~~~
necklace.cpp:139:28: warning: comparison of integer expressions of different signedness: 'std::queue<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
139 | if(q.size()==tmp)
| ~~~~~~~~^~~~~
necklace.cpp:154:27: 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]
154 | for(int l=0; l<t.size()&&aa[0]!=tmp; l++)
| ~^~~~~~~~~
necklace.cpp:156:28: warning: comparison of integer expressions of different signedness: 'std::queue<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
156 | if(q.size()<tmp)
| ~~~~~~~~^~~~
necklace.cpp:170:28: warning: comparison of integer expressions of different signedness: 'std::queue<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
170 | if(q.size()==tmp)
| ~~~~~~~~^~~~~
necklace.cpp:35:9: warning: variable 'ss' set but not used [-Wunused-but-set-variable]
35 | int ss=0;
| ^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
179 ms |
340 KB |
Output is correct |
| 2 |
Correct |
183 ms |
388 KB |
Output is correct |
| 3 |
Correct |
95 ms |
340 KB |
Output is correct |
| 4 |
Correct |
174 ms |
400 KB |
Output is correct |
| 5 |
Correct |
194 ms |
408 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
179 ms |
340 KB |
Output is correct |
| 2 |
Correct |
183 ms |
388 KB |
Output is correct |
| 3 |
Correct |
95 ms |
340 KB |
Output is correct |
| 4 |
Correct |
174 ms |
400 KB |
Output is correct |
| 5 |
Correct |
194 ms |
408 KB |
Output is correct |
| 6 |
Execution timed out |
1596 ms |
528 KB |
Time limit exceeded |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
179 ms |
340 KB |
Output is correct |
| 2 |
Correct |
183 ms |
388 KB |
Output is correct |
| 3 |
Correct |
95 ms |
340 KB |
Output is correct |
| 4 |
Correct |
174 ms |
400 KB |
Output is correct |
| 5 |
Correct |
194 ms |
408 KB |
Output is correct |
| 6 |
Execution timed out |
1596 ms |
528 KB |
Time limit exceeded |
| 7 |
Halted |
0 ms |
0 KB |
- |
