Submission #661040

#	Time	Username	Problem	Language	Result	Execution time	Memory
661040		GusterGoose27	Necklace (Subtask 1-3) (BOI19_necklace1)	C++11	45 / 85	1517 ms	680884 KiB

necklace

#pragma GCC optimize("Ofast")
#pragma GCC target("avx2")

#include <bits/stdc++.h>

using namespace std;

typedef pair<int, int> pii;

const int MAXN = 3000;
const int MAX_s = 4501502;
int n, m;
string s1;
string s2;

class Trie;

Trie *rt;
int to_build[MAX_s];
Trie *tries[MAX_s];
int s = 0, e = 0;
int apos = 0;

class Trie {
public:
	int trans[26];
	int len;
	int prv = -1;
	int arr_pos = 0;
	int par;
	char pchar;
	int s_pos;
	Trie(int par = -1, int l = 0, char pchar = 0, int s_pos = 0) : pchar(pchar), par(par), len(l), s_pos(s_pos) {
		if (l == 0) rt = this;
		fill(trans, trans+26, 0);
		tries[apos] = this;
		arr_pos = apos;
		apos++;
	}
	void build() {
		s++;
		for (int i = 0; i < 26; i++) {
			if (trans[i] > 0) {
				to_build[e++] = trans[i];
			}
		}
		if (len == 0) {
			return;
		}
		if (tries[par]->prv == -1) {
			prv = 0;
		}
		else prv = tries[tries[par]->prv]->trans[pchar];
		for (int i = 0; i < 26; i++) {
			if (trans[i] == 0) trans[i] = tries[prv]->trans[i];
		}
	}
	int ins(char c, int p) {
		if (trans[c] == 0) trans[c] = (new Trie(arr_pos, len+1, c, p))->arr_pos;
		return trans[c];
	}
};

char cur_match[2*MAXN];

bool works(int cur, pii &p) {
	bool found = 0;
	for (int i = 0; i <= m-cur; i++) {
		int pos = 0;
		for (int j = i; j < i+cur; j++) {
			pos = tries[pos]->trans[s2[j]-'a'];
			if (tries[pos]->len == cur) {
				p.first = tries[pos]->s_pos;
				p.second = i;
				found = 1;
				break;
			}
		}
		for (int j = i; j < i+cur-1; j++) {
			pos = tries[pos]->trans[s2[j]-'a'];
			if (tries[pos]->len == cur) {
				p.first = tries[pos]->s_pos;
				p.second = i;
				found = 1;
				break;
			}
		}
		if (found) break;
	}
	if (!found) {
		for (int i = 0; i <= m-cur; i++) {
			int pos = 0;
			for (int j = i+cur-1; j >= i; j--) {
				pos = tries[pos]->trans[s2[j]-'a'];
				if (tries[pos]->len == cur) {
					p.first = tries[pos]->s_pos;
					p.second = i;
					found = 1;
					break;
				}
			}
			for (int j = i+cur-1; j > i; j--) {
				pos = tries[pos]->trans[s2[j]-'a'];
				if (tries[pos]->len == cur) {
					p.first = tries[pos]->s_pos;
					p.second = i;
					found = 1;
					break;
				}
			}
			if (found) break;
		}
	}
	return found;
}

int make_match(pii &p) {
	if (n > 400) {
		int mn = 0;
		int mx = m+1;
		while (mn+1 < mx) {
			int cur = (mn+mx)/2;
			if (works(cur, p)) mn = cur;
			else mx = cur;
		}
		return mn;
	}
	else {
		for (int i = m; i > 0; i--) if (works(i, p)) return i;
	}
}


int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	cin >> s1 >> s2;
	// swap(s1, s2);
	n = s1.size();
	m = s2.size();
	new Trie();
	to_build[e++] = 0;
	for (int i = 0; i < n; i++) {
		int cur = 0;
		for (int j = i; j < n; j++) {
			cur = tries[cur]->ins(s1[j]-'a', i);
		}
	}
	while (s < e) tries[to_build[s]]->build();
	pii p1, p2;
	int b1 = make_match(p1);
	// for (int i = 0; i < m/2; i++) swap(s2[i], s2[m-1-i]);
	// int b2 = make_match(p2);
	// p2.second = m-b2-p2.second;
	// if (b1 < b2) {
	// 	b1 = b2;
	// 	p1 = p2;
	// }
	// swap(p1.first, p1.second);
	cout << b1 << "\n" << p1.first << " " << p1.second << "\n";
}

Compilation message (stderr)

necklace.cpp: In constructor 'Trie::Trie(int, int, char, int)':
necklace.cpp:31:7: warning: 'Trie::pchar' will be initialized after [-Wreorder]
   31 |  char pchar;
      |       ^~~~~
necklace.cpp:30:6: warning:   'int Trie::par' [-Wreorder]
   30 |  int par;
      |      ^~~
necklace.cpp:33:2: warning:   when initialized here [-Wreorder]
   33 |  Trie(int par = -1, int l = 0, char pchar = 0, int s_pos = 0) : pchar(pchar), par(par), len(l), s_pos(s_pos) {
      |  ^~~~
necklace.cpp:30:6: warning: 'Trie::par' will be initialized after [-Wreorder]
   30 |  int par;
      |      ^~~
necklace.cpp:27:6: warning:   'int Trie::len' [-Wreorder]
   27 |  int len;
      |      ^~~
necklace.cpp:33:2: warning:   when initialized here [-Wreorder]
   33 |  Trie(int par = -1, int l = 0, char pchar = 0, int s_pos = 0) : pchar(pchar), par(par), len(l), s_pos(s_pos) {
      |  ^~~~
necklace.cpp: In member function 'void Trie::build()':
necklace.cpp:53:44: warning: array subscript has type 'char' [-Wchar-subscripts]
   53 |   else prv = tries[tries[par]->prv]->trans[pchar];
      |                                            ^~~~~
necklace.cpp: In member function 'int Trie::ins(char, int)':
necklace.cpp:59:13: warning: array subscript has type 'char' [-Wchar-subscripts]
   59 |   if (trans[c] == 0) trans[c] = (new Trie(arr_pos, len+1, c, p))->arr_pos;
      |             ^
necklace.cpp:59:28: warning: array subscript has type 'char' [-Wchar-subscripts]
   59 |   if (trans[c] == 0) trans[c] = (new Trie(arr_pos, len+1, c, p))->arr_pos;
      |                            ^
necklace.cpp:60:16: warning: array subscript has type 'char' [-Wchar-subscripts]
   60 |   return trans[c];
      |                ^
necklace.cpp: In function 'int make_match(pii&)':
necklace.cpp:131:1: warning: control reaches end of non-void function [-Wreturn-type]
  131 | }
      | ^

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