Submission #220143

#	Time	Username	Problem	Language	Result	Execution time	Memory
220143		galca	Necklace (Subtask 1-3) (BOI19_necklace1)	C++14	45 / 85	1621 ms	453880 KiB

necklace

#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 (stderr)

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;
  ~~~^~~~~~~~~~

• Subtask 1: 25 / 25
• Subtask 2: 20 / 20
• Subtask 3: 0 / 40