Submission #125010

#	Time	Username	Problem	Language	Result	Execution time	Memory
125010		gs14004	Necklace (Subtask 1-3) (BOI19_necklace1)	C++17	85 / 85	499 ms	35728 KiB

necklace

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 3005;
using lint = long long;
using pi = pair<int, int>;
 
struct dap{
	int x, y, z;
	bool operator<(const dap &d)const{
		return z < d.z;
	}
};
 
int n, m;
string s, t;
int lcp[MAXN][MAXN];
int sx[MAXN];
int sy[MAXN];

vector<int> getfail(string s){
	vector<int> fail(s.size() + 1);
	int p = 0;
	for(int i=1; i<s.size(); i++){
		while(p && s[p] != s[i]) p = fail[p];
		if(s[p] == s[i]) p++;
		fail[i + 1] = p;
	}
	return fail;
}

dap solve(){
	for(int i=n-1; i>=0; i--){
		for(int j=m-1; j>=0; j--){
			if(s[i] == t[j]) lcp[i][j] = lcp[i+1][j+1] + 1;
			else lcp[i][j] = 0;
		}
	}
	memset(sx, 0x3f, sizeof(sx));
	memset(sy, 0x3f, sizeof(sy));
	dap ret = {-1, -1, -1};

	for(int i=n; i>=0; i--){
		string str;
		for(int j=i-1; j>=0; j--) str.push_back(s[j]);
		str.push_back('$');
		for(int j=m-1; j>=0; j--) str.push_back(t[j]);
		vector<int> f = getfail(str);

		memset(sy, 0x3f, sizeof(sy));
		for(int j=0; j<=m; j++){
			sy[lcp[i][j] + j] = min(sy[lcp[i][j] + j], j);
			sx[j] = min(sx[j], i - f.back());
			f.pop_back();
		}
		for(int j=m; j>=0; j--){
			sy[j] = min(sy[j], sy[j + 1]);
			int minsx = sx[j];
			int minsy = sy[j];
			ret = max(ret, (dap){minsx, minsy, i + j - minsx - minsy});
		}
	}
	return ret;
}
 
int main(){
	cin >> s >> t;
	n = s.size();
	m = t.size();
	auto ret = solve();
	reverse(t.begin(), t.end());
	auto y = solve();
	y.y = m - y.y - y.z;
	ret = max(ret, y);
	cout << ret.z << endl;
	cout << ret.x << " " << ret.y << endl;
}

Compilation message (stderr)

necklace.cpp: In function 'std::vector<int> getfail(std::__cxx11::string)':
necklace.cpp:23:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=1; i<s.size(); i++){
               ~^~~~~~~~~

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