#include <vector>
#include <set>
#include <map>
#include <iostream>
#include <string>
#include <string.h>
using namespace std;
struct NodeInTree {
private:
//NodeInTree* children[26];
map<char, NodeInTree*> children;
public:
set<int> pos;
//int pos;
#if 0
NodeInTree() {
memset(children, 0, 26 * sizeof(NodeInTree*));
}
#endif
NodeInTree* getNext(char c, int pos) {
NodeInTree* next = children[c];
if (next == 0) {
next = createNext(c, pos);
}
this->pos.insert(pos);
return next;
}
NodeInTree* getNext(char c) {
return children[c];
}
NodeInTree* createNext(char c, int pos) {
NodeInTree* next = new NodeInTree();
//next->pos = pos;
next->pos.insert(pos);
children[c] = next;
return next;
}
int getPos() {
return *pos.begin();
}
};
void freeTree(NodeInTree* root) {
for (int i = 'a'; i <= 'z'; i++) {
NodeInTree* n = root->getNext(i);
if (n != 0) {
freeTree(n);
delete n;
}
}
}
void findLongestRing(const char* str1, const char* str2, long long& d, long long& p1, long long& p2) {
//cout << "exec start " << endl;
NodeInTree* stree = new NodeInTree();
int len = strlen(str1);
for (int i = 0; i < len; i++) { // loop over the suffix start
//cout << "string 1 from pos " << i << endl;
NodeInTree* tmp = stree;
//cout << "inserting suffix from pos " << i + 1 << endl;
for (int k = i; k < len; k++) { // loop over the suffix
#if 0
// insert also "wrap around" suffixes
for (int m = 0; m < i; m++) {
NodeInTree* t = tmp;
for (int l = m; l < i; l++) {
//cout << "adding char at pos " << l << " for suffix " << i << endl;
t = t->getNext(str1[l], m);
}
}
#endif
tmp = tmp->getNext(str1[k], i);
}
}
// insert str2
len = strlen(str2);
long long best = 0;
long long bestpos1, bestpos2;
map<int, int> distances[3000];
for (int i = len-1; i >= 0; i--) { // go over suffixes in reverse order //cout << "string 1 from pos " << i << endl;
NodeInTree* tmp = stree;
/* no optimization
if ((len - i) <= best) {
break;
}
*/
NodeInTree* next = tmp->getNext(str2[i]);
if (next != 0) {
for (set<int>::iterator itr = next->pos.begin(); itr != next->pos.end(); itr++) {
distances[i][*itr] = 0;
}
}
int k;
int mybest = 0;
for (k = i; k < len; k++) { // loop over the suffix
NodeInTree* next = tmp->getNext(str2[k]);
if (next == 0) {
break;
}
#if 1
for (set<int>::iterator itr = next->pos.begin(); itr != next->pos.end(); itr++) {
++distances[i][*itr];
}
#endif
tmp = next;
}
if ((k - i) > best) {
best = k - i;
bestpos1 = tmp->getPos();
bestpos2 = i;
//cout << "updating best match for pos " << i << endl;
//cout << "now " << best << endl;
//cout << "string 1 pos " << bestpos1 << endl;
}
}
int len1 = strlen(str1);
int len2 = strlen(str2);
for (int i = 0; i < len2; i++) {
for (map<int, int>::iterator itr = distances[i].begin(); itr != distances[i].end(); itr++) {
int pos1 = i;
int pos2 = (*itr).first;
int d1 = (*itr).second;
int pos3 = pos1 + d1;
if (pos3 < len2) {
for (map<int, int>::iterator itr2 = distances[pos3].begin(); itr2 != distances[pos3].end(); itr2++) {
int pos4 = (*itr2).first;
if (pos4 >= pos2) {
break;
}
int d2 = (*itr2).second;
if (pos4 + d2 >= pos2) {
int total_len = pos2 - pos4 + d1;
if (total_len > best) {
best = total_len;
bestpos2 = pos1;
bestpos1 = pos4;
break;
}
}
}
}
}
}
for (int i = 0; i < len2; i++) {
distances[i].erase(distances[i].begin(), distances[i].end());
}
for (int i = len-1; i >= 0; i--) { // loop over the suffix start //cout << "string 1 from pos " << i << endl;
NodeInTree* tmp = stree;
NodeInTree* next = tmp->getNext(str2[i]);
if (next != 0) {
for (set<int>::iterator itr = next->pos.begin(); itr != next->pos.end(); itr++) {
distances[i][*itr] = 0;
}
}
int k;
for (k = i; k < len; k++) { // loop over the suffix
NodeInTree* next = tmp->getNext(str2[len - k - 1]);
if (next == 0) {
break;
}
#if 1
for (set<int>::iterator itr = next->pos.begin(); itr != next->pos.end(); itr++) {
++distances[i][*itr];
}
#endif
tmp = next;
}
if ((k - i) > best) {
best = k - i;
bestpos1 = tmp->getPos();
bestpos2 = len - k;
//cout << "updating best match for inverse pos " << i << endl;
//cout << "now " << best << endl;
//cout << "string 1 pos " << bestpos1 << endl;
}
}
for (int i = 0; i < len2; i++) {
for (map<int, int>::iterator itr = distances[i].begin(); itr != distances[i].end(); itr++) {
int pos2 = (*itr).first;
int d1 = (*itr).second;
int pos3 = i + d1;
if (pos3 < len2) {
for (map<int, int>::iterator itr2 = distances[pos3].begin(); itr2 != distances[pos3].end(); itr2++) {
int pos4 = (*itr2).first;
if (pos4 >= pos2) {
break;
}
int d2 = (*itr2).second;
if (pos4 + d2 >= pos2) {
int total_len = pos2 - pos4 + d1;
if (total_len > best) {
best = total_len;
bestpos2 = len - (i + total_len);
bestpos1 = pos4;
//cout << "updating len to " << total_len << endl;
//cout << "i " << i << " d1 " << d1 << " pos2 " << pos2 << " pos4 " << pos4 << " d2 " << d2 << endl;
//cout << "str2 len is " << len << endl;
break;
}
}
}
}
}
}
/*
for (int i = 0; i < len2; i++) {
distances[i].erase(distances[i].begin(), distances[i].end());
}*/
d = best;
p1 = bestpos1;
p2 = bestpos2;
//freeTree(stree);
}
int main() {
string str1, str2;
cin >> str1;
cin >> str2;
long long d1, p12, p11;
#if 1
if (str1.length() > str2.length()) {
findLongestRing(str1.c_str(), str2.c_str(), d1, p11, p12);
}
else {
findLongestRing(str2.c_str(), str1.c_str(), d1, p12, p11);
}
#endif
cout << d1 << endl;
cout << p11 << " " << p12 << endl;
#if 0
for (int i = p11; i < p11 + d1; i++) {
cout << str1[i];
}
cout << endl;
for (int i = p12; i < p12 + d1; i++) {
cout << str2[i];
}
cout << endl;
#endif
return 0;
}
Compilation message
necklace.cpp: In function 'void findLongestRing(const char*, const char*, long long int&, long long int&, long long int&)':
necklace.cpp:111:7: warning: unused variable 'mybest' [-Wunused-variable]
int mybest = 0;
^~~~~~
necklace.cpp:133:6: warning: unused variable 'len1' [-Wunused-variable]
int len1 = strlen(str1);
^~~~
necklace.cpp:237:5: warning: 'bestpos2' may be used uninitialized in this function [-Wmaybe-uninitialized]
p2 = bestpos2;
~~~^~~~~~~~~~
necklace.cpp:236:5: warning: 'bestpos1' may be used uninitialized in this function [-Wmaybe-uninitialized]
p1 = bestpos1;
~~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
18 ms |
1280 KB |
Output is correct |
| 2 |
Correct |
12 ms |
1280 KB |
Output is correct |
| 3 |
Correct |
11 ms |
1664 KB |
Output is correct |
| 4 |
Correct |
9 ms |
1664 KB |
Output is correct |
| 5 |
Correct |
6 ms |
1536 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
18 ms |
1280 KB |
Output is correct |
| 2 |
Correct |
12 ms |
1280 KB |
Output is correct |
| 3 |
Correct |
11 ms |
1664 KB |
Output is correct |
| 4 |
Correct |
9 ms |
1664 KB |
Output is correct |
| 5 |
Correct |
6 ms |
1536 KB |
Output is correct |
| 6 |
Correct |
1056 ms |
14536 KB |
Output is correct |
| 7 |
Correct |
309 ms |
13180 KB |
Output is correct |
| 8 |
Correct |
449 ms |
21496 KB |
Output is correct |
| 9 |
Correct |
244 ms |
22136 KB |
Output is correct |
| 10 |
Correct |
28 ms |
18304 KB |
Output is correct |
| 11 |
Correct |
33 ms |
18304 KB |
Output is correct |
| 12 |
Correct |
325 ms |
19448 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
18 ms |
1280 KB |
Output is correct |
| 2 |
Correct |
12 ms |
1280 KB |
Output is correct |
| 3 |
Correct |
11 ms |
1664 KB |
Output is correct |
| 4 |
Correct |
9 ms |
1664 KB |
Output is correct |
| 5 |
Correct |
6 ms |
1536 KB |
Output is correct |
| 6 |
Correct |
1056 ms |
14536 KB |
Output is correct |
| 7 |
Correct |
309 ms |
13180 KB |
Output is correct |
| 8 |
Correct |
449 ms |
21496 KB |
Output is correct |
| 9 |
Correct |
244 ms |
22136 KB |
Output is correct |
| 10 |
Correct |
28 ms |
18304 KB |
Output is correct |
| 11 |
Correct |
33 ms |
18304 KB |
Output is correct |
| 12 |
Correct |
325 ms |
19448 KB |
Output is correct |
| 13 |
Execution timed out |
1621 ms |
453880 KB |
Time limit exceeded |
| 14 |
Halted |
0 ms |
0 KB |
- |
