#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
const long long mod = 100000000007LL;
string S, T;
vector<long long> vec[3009];
long long power[3009];
void init() {
power[0] = 1LL;
for (int i = 1; i <= 3000; i++) power[i] = (101LL * power[i - 1]);
}
long long hash_val(string &U) {
long long r = 0;
for (int i = 0; i < U.size(); i++) {
r *= 101LL;
r += (long long)(U[i] - 'a' + 1LL);
}
return r;
}
vector<long long> get_substring(string &U) {
vector<long long> a, b, c;
a.push_back(0);
for (int i = 0; i < U.size(); i++) {
a.push_back((101LL * a[a.size() - 1] + (long long)(U[i] - 'a' + 1)));
}
b.push_back(0);
for (int i = U.size() - 1; i >= 0; i--) {
b.push_back((b[b.size() - 1] + power[U.size() - 1 - i] * (long long)(U[i] - 'a' + 1)));
}
reverse(b.begin(), b.end());
for (int i = 0; i < U.size(); i++) {
long long s = a[i] + power[i] * b[i];
c.push_back(s);
}
return c;
}
int main() {
init();
cin >> S >> T;
for (int i = 0; i < S.size(); i++) {
string G = "";
for (int j = i + 1; j <= S.size(); j++) {
G += S[j - 1];
vector<long long> V1 = get_substring(G);
for (int k = 0; k < V1.size(); k++) {
vec[j - i].push_back((((V1[k] % mod) + mod) << 20) + 1LL * i);
}
}
}
for (int i = 0; i <= S.size(); i++) sort(vec[i].begin(), vec[i].end());
int maxn = 0; pair<int, int> maxid = make_pair(-1, -1);
for (int i = 0; i < T.size(); i++) {
string G = "";
for (int j = i + 1; j <= T.size(); j++) {
G += T[j - 1];
long long v = hash_val(G); v = (v % mod) + mod;
int pos1 = lower_bound(vec[j - i].begin(), vec[j - i].end(), v << 20) - vec[j - i].begin();
if (pos1 < vec[j - i].size() && (vec[j - i][pos1] >> 20) == v) {
if (maxn < j - i) {
maxn = j - i;
maxid = make_pair(vec[j - i][pos1] % (1LL << 20), i);
}
}
}
}
for (int i = 1; i <= T.size(); i++) {
string G = "";
for (int j = i - 1; j >= 0; j--) {
G += T[j];
long long v = hash_val(G); v = (v % mod) + mod;
int pos1 = lower_bound(vec[i - j].begin(), vec[i - j].end(), v << 20) - vec[i - j].begin();
if (pos1 < vec[i - j].size() && (vec[i - j][pos1] >> 20) == v) {
if (maxn < i - j) {
maxn = i - j;
maxid = make_pair(vec[i - j][pos1] % (1LL << 20), j);
}
}
}
}
cout << maxn << endl;
cout << maxid.first << " " << maxid.second << endl;
return 0;
}
Compilation message
necklace.cpp: In function 'long long int hash_val(std::__cxx11::string&)':
necklace.cpp:21:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < U.size(); i++) {
~~^~~~~~~~~~
necklace.cpp: In function 'std::vector<long long int> get_substring(std::__cxx11::string&)':
necklace.cpp:31:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < U.size(); i++) {
~~^~~~~~~~~~
necklace.cpp:40:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < U.size(); i++) {
~~^~~~~~~~~~
necklace.cpp: In function 'int main()':
necklace.cpp:50:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < S.size(); i++) {
~~^~~~~~~~~~
necklace.cpp:52:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int j = i + 1; j <= S.size(); j++) {
~~^~~~~~~~~~~
necklace.cpp:55:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int k = 0; k < V1.size(); k++) {
~~^~~~~~~~~~~
necklace.cpp:60:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i <= S.size(); i++) sort(vec[i].begin(), vec[i].end());
~~^~~~~~~~~~~
necklace.cpp:63:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < T.size(); i++) {
~~^~~~~~~~~~
necklace.cpp:65:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int j = i + 1; j <= T.size(); j++) {
~~^~~~~~~~~~~
necklace.cpp:70:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if (pos1 < vec[j - i].size() && (vec[j - i][pos1] >> 20) == v) {
~~~~~^~~~~~~~~~~~~~~~~~~
necklace.cpp:79:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 1; i <= T.size(); i++) {
~~^~~~~~~~~~~
necklace.cpp:86:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if (pos1 < vec[i - j].size() && (vec[i - j][pos1] >> 20) == v) {
~~~~~^~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
21 ms |
2296 KB |
Output is correct |
| 2 |
Correct |
23 ms |
2296 KB |
Output is correct |
| 3 |
Correct |
14 ms |
1400 KB |
Output is correct |
| 4 |
Correct |
24 ms |
2296 KB |
Output is correct |
| 5 |
Correct |
24 ms |
2168 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
21 ms |
2296 KB |
Output is correct |
| 2 |
Correct |
23 ms |
2296 KB |
Output is correct |
| 3 |
Correct |
14 ms |
1400 KB |
Output is correct |
| 4 |
Correct |
24 ms |
2296 KB |
Output is correct |
| 5 |
Correct |
24 ms |
2168 KB |
Output is correct |
| 6 |
Correct |
978 ms |
94012 KB |
Output is correct |
| 7 |
Correct |
1277 ms |
93976 KB |
Output is correct |
| 8 |
Correct |
1311 ms |
88288 KB |
Output is correct |
| 9 |
Correct |
1288 ms |
80868 KB |
Output is correct |
| 10 |
Correct |
1424 ms |
92044 KB |
Output is correct |
| 11 |
Correct |
1402 ms |
91208 KB |
Output is correct |
| 12 |
Correct |
1276 ms |
82456 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
21 ms |
2296 KB |
Output is correct |
| 2 |
Correct |
23 ms |
2296 KB |
Output is correct |
| 3 |
Correct |
14 ms |
1400 KB |
Output is correct |
| 4 |
Correct |
24 ms |
2296 KB |
Output is correct |
| 5 |
Correct |
24 ms |
2168 KB |
Output is correct |
| 6 |
Correct |
978 ms |
94012 KB |
Output is correct |
| 7 |
Correct |
1277 ms |
93976 KB |
Output is correct |
| 8 |
Correct |
1311 ms |
88288 KB |
Output is correct |
| 9 |
Correct |
1288 ms |
80868 KB |
Output is correct |
| 10 |
Correct |
1424 ms |
92044 KB |
Output is correct |
| 11 |
Correct |
1402 ms |
91208 KB |
Output is correct |
| 12 |
Correct |
1276 ms |
82456 KB |
Output is correct |
| 13 |
Execution timed out |
1584 ms |
415244 KB |
Time limit exceeded |
| 14 |
Halted |
0 ms |
0 KB |
- |
