| # | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 219993 | 2020-04-06T19:06:15 Z | galca | Necklace (Subtask 1-3) (BOI19_necklace1) | C++14 | 22 ms | 1280 KB |
#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;
}
*/
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++) {
if (distances[i].find(*itr) != distances[i].end()) {
++distances[i][*itr];
}
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;
}
}
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) {
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;
}
}
}
}
}
}
}
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;
/* 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;
}
#if 1
for (set<int>::iterator itr = next->pos.begin(); itr != next->pos.end(); itr++) {
if (distances[i].find(*itr) != distances[i].end()) {
++distances[i][*itr];
}
else {
distances[k][*itr] = 1;
}
}
#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 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) {
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;
}
}
}
}
}
}
}
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, 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;
}
Compilation message
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 22 ms | 1280 KB | Output is correct |
| 2 | Incorrect | 12 ms | 1152 KB | Output isn't correct |
| 3 | Halted | 0 ms | 0 KB | - |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 22 ms | 1280 KB | Output is correct |
| 2 | Incorrect | 12 ms | 1152 KB | Output isn't correct |
| 3 | Halted | 0 ms | 0 KB | - |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 22 ms | 1280 KB | Output is correct |
| 2 | Incorrect | 12 ms | 1152 KB | Output isn't correct |
| 3 | Halted | 0 ms | 0 KB | - |