#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=11; 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-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=11; 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: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:118: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]
118 | if(tmp<=s.size()&&tmp<=t.size())
| ~~~^~~~~~~~~~
necklace.cpp:118: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]
118 | if(tmp<=s.size()&&tmp<=t.size())
| ~~~^~~~~~~~~~
necklace.cpp:123: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]
123 | for(int l=0; l<s.size(); l++)
| ~^~~~~~~~~
necklace.cpp:126: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]
126 | if(q.size()<tmp)
| ~~~~~~~~^~~~
necklace.cpp:140: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]
140 | if(q.size()==tmp)
| ~~~~~~~~^~~~~
necklace.cpp:155: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]
155 | for(int l=0; l<t.size()&&aa[0]!=tmp; l++)
| ~^~~~~~~~~
necklace.cpp:157: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]
157 | if(q.size()<tmp)
| ~~~~~~~~^~~~
necklace.cpp:171: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]
171 | if(q.size()==tmp)
| ~~~~~~~~^~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
14 ms |
320 KB |
Output is correct |
| 2 |
Partially correct |
12 ms |
364 KB |
Output is partially correct |
| 3 |
Correct |
11 ms |
340 KB |
Output is correct |
| 4 |
Correct |
14 ms |
400 KB |
Output is correct |
| 5 |
Correct |
11 ms |
340 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
14 ms |
320 KB |
Output is correct |
| 2 |
Partially correct |
12 ms |
364 KB |
Output is partially correct |
| 3 |
Correct |
11 ms |
340 KB |
Output is correct |
| 4 |
Correct |
14 ms |
400 KB |
Output is correct |
| 5 |
Correct |
11 ms |
340 KB |
Output is correct |
| 6 |
Correct |
216 ms |
1100 KB |
Output is correct |
| 7 |
Partially correct |
331 ms |
1788 KB |
Output is partially correct |
| 8 |
Correct |
300 ms |
716 KB |
Output is correct |
| 9 |
Correct |
259 ms |
2088 KB |
Output is correct |
| 10 |
Correct |
311 ms |
2484 KB |
Output is correct |
| 11 |
Correct |
206 ms |
2372 KB |
Output is correct |
| 12 |
Correct |
305 ms |
1888 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
14 ms |
320 KB |
Output is correct |
| 2 |
Partially correct |
12 ms |
364 KB |
Output is partially correct |
| 3 |
Correct |
11 ms |
340 KB |
Output is correct |
| 4 |
Correct |
14 ms |
400 KB |
Output is correct |
| 5 |
Correct |
11 ms |
340 KB |
Output is correct |
| 6 |
Correct |
216 ms |
1100 KB |
Output is correct |
| 7 |
Partially correct |
331 ms |
1788 KB |
Output is partially correct |
| 8 |
Correct |
300 ms |
716 KB |
Output is correct |
| 9 |
Correct |
259 ms |
2088 KB |
Output is correct |
| 10 |
Correct |
311 ms |
2484 KB |
Output is correct |
| 11 |
Correct |
206 ms |
2372 KB |
Output is correct |
| 12 |
Correct |
305 ms |
1888 KB |
Output is correct |
| 13 |
Execution timed out |
1591 ms |
65200 KB |
Time limit exceeded |
| 14 |
Halted |
0 ms |
0 KB |
- |
