#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
#define fastio ios::sync_with_stdio(false), cin.tie(0)
#pragma GCC optimize("Ofast")
#define pb push_back
#define eb emplace_back
#define f first
#define s second
#define int long long
#define lowbit(x) x&-x
const int INF = 1e18;
const int maxn = 1e5 + 5;
const int N = 1e9 + 7;
const int A = 923482345;
int p[maxn];
map<int, int> mp;
pll ans = {0, 0};
int smallest_cyclic_shift(string s){
s = s + s;
int n = s.size();
vector<int> st;
int i = 0;
while(i < n){
int j = i + 1, k = i;
while(j < n && s[k] <= s[j]){
if(s[k] < s[j]) k = i;
else k++;
j++;
}
while(i <= k){
st.pb(i);
i += j - k;
}
}
for(int i = 0; i < st.size(); i++){
if(i == st.size() - 1 || (st[i] < n / 2 && st[i + 1] >= n / 2)){
return st[i];
}
}
return 0;
}
int hashs(string s, int id){
string nw = s.substr(id) + s.substr(0, id);
int ret = 0;
for(int i = 0; i < s.size(); i++) (ret += p[i] * nw[i]) %= N;
// cout<<"hash : "<<nw<<" "<<ret<<"\n";
return ret;
}
signed main(void){
fastio;
string s, t;
cin>>s>>t;
int n = max(s.size(), t.size());
p[0] = 1;
for(int i = 1; i < n; i++) p[i] = p[i - 1] * A % N;
int l = 0, r = n + 1;
while(l + 1 < r){
mp.clear();
int m = (l + r) / 2;
for(int i = 0; i + m - 1 < s.size(); i++){
string nw = "";
for(int j = 0; j < m; j++) nw += s[i + j];
int id = smallest_cyclic_shift(nw);
// cout<<nw<<" "<<id<<"\n";
// cout<<"put : "<<hashs(nw, id)<<"\n";
mp[hashs(nw, id)] = i + 1;
reverse(nw.begin(), nw.end());
id = smallest_cyclic_shift(nw);
mp[hashs(nw, id)] = i + 1;
}
int ok = 0;
for(int i = 0; i + m - 1 < t.size(); i++){
string nw = "";
for(int j = 0; j < m; j++) nw += t[i + j];
int id = smallest_cyclic_shift(nw);
if(mp.find(hashs(nw, id)) != mp.end()){
ans = {mp[hashs(nw, id)], i + 1};
ok = 1;
break;
}
reverse(nw.begin(), nw.end());
id = smallest_cyclic_shift(nw);
// cout<<"search : "<<hashs(nw, id)<<"\n";
if(mp.find(hashs(nw, id)) != mp.end()){
ans = {mp[hashs(nw, id)], i + 1};
ok = 1;
break;
}
}
if(ok) l = m;
else r = m;
}
cout<<l<<"\n";
cout<<ans.f<<" "<<ans.s<<"\n";
}
Compilation message
necklace.cpp: In function 'long long int smallest_cyclic_shift(std::string)':
necklace.cpp:38:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
38 | for(int i = 0; i < st.size(); i++){
| ~~^~~~~~~~~~~
necklace.cpp:39:8: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
39 | if(i == st.size() - 1 || (st[i] < n / 2 && st[i + 1] >= n / 2)){
| ~~^~~~~~~~~~~~~~~~
necklace.cpp: In function 'long long int hashs(std::string, long long int)':
necklace.cpp:48:19: 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]
48 | for(int i = 0; i < s.size(); i++) (ret += p[i] * nw[i]) %= N;
| ~~^~~~~~~~~~
necklace.cpp: In function 'int main()':
necklace.cpp:63:28: 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]
63 | for(int i = 0; i + m - 1 < s.size(); i++){
| ~~~~~~~~~~^~~~~~~~~~
necklace.cpp:75:28: 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]
75 | for(int i = 0; i + m - 1 < t.size(); i++){
| ~~~~~~~~~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
