#include <bits/stdc++.h>
#define suiii ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define ll long long
#define co cout<<
//#pragma GCC optimize("O3,Ofast,unroll-loops")
//#pragma GCC target("avx2,sse3,sse4,avx")
using namespace std;
//stuff
const ll maxn=405,mod=1e9+7,base=3005;
string s,s1;
ll ha[maxn][maxn];
ll ha1[maxn][maxn];
void solve(){
cin>>s>>s1;
if(s.size()>s1.size()) swap(s,s1);
s='#'+s;
s1='#'+s1;
for(int i=1;i<s.size();i++){
ll freq[27]={};
for(int j=i;j<s.size();j++){
freq[s[j]-'a']++;
for(int k=0;k<27;k++) ha[i][j]=(ha[i][j]*base+freq[k])%mod;
}
}
for(int i=1;i<s1.size();i++){
ll freq[27]={};
for(int j=i;j<s1.size();j++){
freq[s1[j]-'a']++;
for(int k=0;k<27;k++) ha1[i][j]=(ha1[i][j]*base+freq[k])%mod;
}
}
for(int k=s.size()-1;k>=1;k--){
for(int i=1;i<s.size();i++){
if(i+k-1>=s.size()) break;
for(int j=1;j<s1.size()-k+1;j++){
if(j+k-1>=s1.size()) break;
if(ha[i][i+k-1]==ha1[j][j+k-1]){
// co ha[i][i+k-1]<<' '<<ha1[j][j+k-1]<<'\n';
// co s.substr(i,k)<<' '<<s1.substr(j,k)<<'\n';
co k<<'\n'<<i-1<<' '<<j-1;
return;
}
}
}
}
}
int main()
{
suiii
int tt=1;
// cin>>tt;
while(tt--){
solve();
}
return 0;
}
Compilation message
necklace.cpp: In function 'void solve()':
necklace.cpp:19:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
19 | for(int i=1;i<s.size();i++){
| ~^~~~~~~~~
necklace.cpp:21:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
21 | for(int j=i;j<s.size();j++){
| ~^~~~~~~~~
necklace.cpp:26:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
26 | for(int i=1;i<s1.size();i++){
| ~^~~~~~~~~~
necklace.cpp:28:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
28 | for(int j=i;j<s1.size();j++){
| ~^~~~~~~~~~
necklace.cpp:34:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
34 | for(int i=1;i<s.size();i++){
| ~^~~~~~~~~
necklace.cpp:35:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
35 | if(i+k-1>=s.size()) break;
| ~~~~~^~~~~~~~~~
necklace.cpp:36:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
36 | for(int j=1;j<s1.size()-k+1;j++){
| ~^~~~~~~~~~~~~~
necklace.cpp:37:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
37 | if(j+k-1>=s1.size()) break;
| ~~~~~^~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
856 KB |
Output is correct |
| 2 |
Correct |
2 ms |
1100 KB |
Output is correct |
| 3 |
Correct |
1 ms |
860 KB |
Output is correct |
| 4 |
Incorrect |
1 ms |
860 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
856 KB |
Output is correct |
| 2 |
Correct |
2 ms |
1100 KB |
Output is correct |
| 3 |
Correct |
1 ms |
860 KB |
Output is correct |
| 4 |
Incorrect |
1 ms |
860 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
856 KB |
Output is correct |
| 2 |
Correct |
2 ms |
1100 KB |
Output is correct |
| 3 |
Correct |
1 ms |
860 KB |
Output is correct |
| 4 |
Incorrect |
1 ms |
860 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
