#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;
if(min(s.size(), t.size())<=100)
{
array<int, 3> aa={0, 0, 0};
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];
}
else
{ for(int i=8; i>=0; i--)
{
int tmp=ss+(1<<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(l<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(l<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=8; i>=0; i--)
{
int tmp=ss+(1<<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:45:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'const long unsigned int' [-Wsign-compare]
45 | for(int i=1; i<min(s.size(), t.size()); i++)
| ~^~~~~~~~~~~~~~~~~~~~~~~~
necklace.cpp:49: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]
49 | if(tmp<=s.size()&&tmp<=t.size())
| ~~~^~~~~~~~~~
necklace.cpp:49: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]
49 | if(tmp<=s.size()&&tmp<=t.size())
| ~~~^~~~~~~~~~
necklace.cpp:54: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]
54 | for(int l=0; l<s.size(); l++)
| ~^~~~~~~~~
necklace.cpp:57: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]
57 | if(q.size()<tmp)
| ~~~~~~~~^~~~
necklace.cpp:71: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]
71 | if(q.size()==tmp)
| ~~~~~~~~^~~~~
necklace.cpp:86: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]
86 | for(int l=0; l<t.size()&&aa[0]!=tmp; l++)
| ~^~~~~~~~~
necklace.cpp:88: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]
88 | if(q.size()<tmp)
| ~~~~~~~~^~~~
necklace.cpp:102: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]
102 | if(q.size()==tmp)
| ~~~~~~~~^~~~~
necklace.cpp:119:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'const long unsigned int' [-Wsign-compare]
119 | for(int i=1; i<min(s.size(), t.size()); i++)
| ~^~~~~~~~~~~~~~~~~~~~~~~~
necklace.cpp:122: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]
122 | if(tmp<=s.size()&&tmp<=t.size())
| ~~~^~~~~~~~~~
necklace.cpp:122: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]
122 | if(tmp<=s.size()&&tmp<=t.size())
| ~~~^~~~~~~~~~
necklace.cpp:127: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]
127 | for(int l=0; l<s.size(); l++)
| ~^~~~~~~~~
necklace.cpp:130: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]
130 | if(q.size()<tmp)
| ~~~~~~~~^~~~
necklace.cpp:144: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]
144 | if(q.size()==tmp)
| ~~~~~~~~^~~~~
necklace.cpp:159: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]
159 | for(int l=0; l<t.size()&&aa[0]!=tmp; l++)
| ~^~~~~~~~~
necklace.cpp:161: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]
161 | if(q.size()<tmp)
| ~~~~~~~~^~~~
necklace.cpp:175: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]
175 | if(q.size()==tmp)
| ~~~~~~~~^~~~~
necklace.cpp:194: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]
194 | if(tmp<=s.size()&&tmp<=t.size())
| ~~~^~~~~~~~~~
necklace.cpp:194: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]
194 | if(tmp<=s.size()&&tmp<=t.size())
| ~~~^~~~~~~~~~
necklace.cpp:199: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]
199 | for(int l=0; l<s.size(); l++)
| ~^~~~~~~~~
necklace.cpp:216: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]
216 | if(q.size()==tmp)
| ~~~~~~~~^~~~~
necklace.cpp:231: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]
231 | for(int l=0; l<t.size()&&aa[0]!=tmp; l++)
| ~^~~~~~~~~
necklace.cpp:247: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]
247 | if(q.size()==tmp)
| ~~~~~~~~^~~~~
necklace.cpp:268: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]
268 | if(tmp<=s.size()&&tmp<=t.size())
| ~~~^~~~~~~~~~
necklace.cpp:268: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]
268 | if(tmp<=s.size()&&tmp<=t.size())
| ~~~^~~~~~~~~~
necklace.cpp:273: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]
273 | for(int l=0; l<s.size(); l++)
| ~^~~~~~~~~
necklace.cpp:276: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]
276 | if(q.size()<tmp)
| ~~~~~~~~^~~~
necklace.cpp:290: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]
290 | if(q.size()==tmp)
| ~~~~~~~~^~~~~
necklace.cpp:305: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]
305 | for(int l=0; l<t.size()&&aa[0]!=tmp; l++)
| ~^~~~~~~~~
necklace.cpp:307: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]
307 | if(q.size()<tmp)
| ~~~~~~~~^~~~
necklace.cpp:321: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]
321 | if(q.size()==tmp)
| ~~~~~~~~^~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
192 ms |
468 KB |
Output is correct |
| 2 |
Correct |
187 ms |
396 KB |
Output is correct |
| 3 |
Correct |
103 ms |
340 KB |
Output is correct |
| 4 |
Correct |
183 ms |
464 KB |
Output is correct |
| 5 |
Correct |
198 ms |
452 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
192 ms |
468 KB |
Output is correct |
| 2 |
Correct |
187 ms |
396 KB |
Output is correct |
| 3 |
Correct |
103 ms |
340 KB |
Output is correct |
| 4 |
Correct |
183 ms |
464 KB |
Output is correct |
| 5 |
Correct |
198 ms |
452 KB |
Output is correct |
| 6 |
Correct |
217 ms |
944 KB |
Output is correct |
| 7 |
Partially correct |
341 ms |
1680 KB |
Output is partially correct |
| 8 |
Correct |
293 ms |
512 KB |
Output is correct |
| 9 |
Correct |
269 ms |
2028 KB |
Output is correct |
| 10 |
Correct |
308 ms |
2408 KB |
Output is correct |
| 11 |
Correct |
222 ms |
2416 KB |
Output is correct |
| 12 |
Correct |
319 ms |
1908 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
192 ms |
468 KB |
Output is correct |
| 2 |
Correct |
187 ms |
396 KB |
Output is correct |
| 3 |
Correct |
103 ms |
340 KB |
Output is correct |
| 4 |
Correct |
183 ms |
464 KB |
Output is correct |
| 5 |
Correct |
198 ms |
452 KB |
Output is correct |
| 6 |
Correct |
217 ms |
944 KB |
Output is correct |
| 7 |
Partially correct |
341 ms |
1680 KB |
Output is partially correct |
| 8 |
Correct |
293 ms |
512 KB |
Output is correct |
| 9 |
Correct |
269 ms |
2028 KB |
Output is correct |
| 10 |
Correct |
308 ms |
2408 KB |
Output is correct |
| 11 |
Correct |
222 ms |
2416 KB |
Output is correct |
| 12 |
Correct |
319 ms |
1908 KB |
Output is correct |
| 13 |
Execution timed out |
1573 ms |
16712 KB |
Time limit exceeded |
| 14 |
Halted |
0 ms |
0 KB |
- |
