#include<bits/stdc++.h>
using namespace std;
signed main(){
ios::sync_with_stdio(0); cin.tie(0);
// freopen("input.txt","r",stdin);
//freopen("output.txt","w",stdout);
string s, t;
map<vector<int>, int> pos;
cin >> s >> t;
int res = 0, p1 = -1, p2 = -1;
for (int i = 0 ; i < s.size() ; i++) {
for (int j = 0 ; j < t.size() ; j++) {
if (s[i] == t[j]) {
res = 1;
p1 = i;
p2 = j;
break;
}
}
}
for (int i = 0 ; i + 1 < s.size() ; i++) {
vector<int> graph(26 * 26);
graph[(s[i]-'a') * 26 + (s[i+1]-'a')] += 1;
graph[(s[i+1]-'a') * 26 + (s[i]-'a')] += 1;
for (int j = i + 2 ; j < s.size() ; j++) {
graph[(s[i]-'a') * 26 + (s[j]-'a')] += 1;
graph[(s[j]-'a') * 26 + (s[i]-'a')] += 1;
if (j != i + 2) {
graph[(s[j-1]-'a') * 26 + (s[i]-'a')] -= 1;
graph[(s[i]-'a') * 26 + (s[j-1]-'a')] -= 1;
}
graph[(s[j-1]-'a') * 26 + s[j]-'a'] += 1;
graph[(s[j]-'a') * 26 + s[j-1]-'a'] += 1;
pos[graph] = i;
}
}
s = t;
for (int i = 0 ; i + 1 < s.size() ; i++) {
vector<int> graph(26 * 26);
graph[(s[i]-'a') * 26 + (s[i+1]-'a')] += 1;
graph[(s[i+1]-'a') * 26 + (s[i]-'a')] += 1;
for (int j = i + 2 ; j < s.size() ; j++) {
graph[(s[i]-'a') * 26 + (s[j]-'a')] += 1;
graph[(s[j]-'a') * 26 + (s[i]-'a')] += 1;
if (j != i + 2) {
graph[(s[j-1]-'a') * 26 + (s[i]-'a')] -= 1;
graph[(s[i]-'a') * 26 + (s[j-1]-'a')] -= 1;
}
graph[(s[j-1]-'a') * 26 + s[j]-'a'] += 1;
graph[(s[j]-'a') * 26 + s[j-1]-'a'] += 1;
if (j-i+1 > res && pos.find(graph) != pos.end()) {
res = j - i + 1;
p1 = pos[graph];
p2 = i;
}
}
}
cout << res << "\n" << p1 << " " << p2;
return 0;
}
Compilation message
necklace.cpp: In function 'int main()':
necklace.cpp:18:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
18 | for (int i = 0 ; i < s.size() ; i++) {
| ~~^~~~~~~~~~
necklace.cpp:19:28: 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 j = 0 ; j < t.size() ; j++) {
| ~~^~~~~~~~~~
necklace.cpp:29:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
29 | for (int i = 0 ; i + 1 < s.size() ; i++) {
| ~~~~~~^~~~~~~~~~
necklace.cpp:33:32: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
33 | for (int j = i + 2 ; j < s.size() ; j++) {
| ~~^~~~~~~~~~
necklace.cpp:48:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
48 | for (int i = 0 ; i + 1 < s.size() ; i++) {
| ~~~~~~^~~~~~~~~~
necklace.cpp:52:32: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
52 | for (int j = i + 2 ; j < s.size() ; j++) {
| ~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
21 ms |
5212 KB |
Output is correct |
| 2 |
Correct |
10 ms |
4636 KB |
Output is correct |
| 3 |
Correct |
11 ms |
2652 KB |
Output is correct |
| 4 |
Incorrect |
16 ms |
3928 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
21 ms |
5212 KB |
Output is correct |
| 2 |
Correct |
10 ms |
4636 KB |
Output is correct |
| 3 |
Correct |
11 ms |
2652 KB |
Output is correct |
| 4 |
Incorrect |
16 ms |
3928 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
21 ms |
5212 KB |
Output is correct |
| 2 |
Correct |
10 ms |
4636 KB |
Output is correct |
| 3 |
Correct |
11 ms |
2652 KB |
Output is correct |
| 4 |
Incorrect |
16 ms |
3928 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
