| # | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 219954 | 2020-04-06T17:55:55 Z | galca | Necklace (Subtask 1-3) (BOI19_necklace1) | C++14 | 0 ms | 0 KB |
#include <vector>
#include <set>
#include <map>
#include <iostream>
#include <string>
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);
}
return next;
}
NodeInTree* getNext(char c) {
return children[c];
}
NodeInTree* createNext(char c, int pos) {
NodeInTree* next = new NodeInTree();
this->pos = pos;
children[c] = next;
return next;
}
int getPos() {
return pos;
}
};
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;
}
*/
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 0
++mybest;
for (set<int>::iterator itr = next->pos.begin(); itr != next->pos.end(); itr++) {
if (distances[i].find(*itr) != distances[i].end()) {
++distances[i][*itr];
if (distances[k + 1][*itr - (k - i)] != 0) {
}
}
else {
distances[k][*itr] = 1;
}
}
#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;
}
}
for (int i = len-1; i >= 0; i--) { // loop over the suffix start //cout << "string 1 from pos " << i << endl;
NodeInTree* tmp = stree;
/* no opt
if ((len - i) <= best) {
break;
}*/
int k;
for (k = i; k < len; k++) { // loop over the suffix
NodeInTree* next = tmp->getNext(str2[len - k - 1]);
if (next == 0) {
break;
}
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;
}
}
d = best;
p1 = bestpos1;
p2 = bestpos2;
//freeTree(stree);
}
int main() {
string str1, str2;
cin >> str1;
cin >> str2;
long long d1, d2, p11, p12, p21, p22;
#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;
return 0;
}