Submission #577229

#	Time	Username	Problem	Language	Result	Execution time	Memory
577229		zhangjishen	Necklace (Subtask 4) (BOI19_necklace4)	C++98	15 / 15	216 ms	520 KiB

necklace

#include<bits/stdc++.h>
using namespace std;

#define pb push_back
template<typename T> bool chkmin(T &a, T b){return b < a ? a = b, 1 : 0;}
template<typename T> bool chkmax(T &a, T b){return b > a ? a = b, 1 : 0;}

vector<int> kmp(string s, string t){
	vector<int> nxt(s.size(), 0), mat(t.size(), 0);
	if(s.size() == 0) return mat;	// empty pattern
	nxt[0] = 0;
	for(int i = 1; i < (int)s.size(); i++){
		int len = nxt[i - 1];
		while(len > 0 && s[len] != s[i]) 
			len = nxt[len - 1];
		if(s[i] == s[len]) len++;
		nxt[i] = len;
	}
	int len = 0;
	for(int i = 0; i < (int)t.size(); i++){
		while(len > 0 && t[i] != s[len])
			len = nxt[len - 1];
		if(t[i] == s[len]) len++;
		mat[i] = len;
		if(len == (int)s.size())
			len = nxt[len - 1];
	}
	return mat;
}

int n, m;
string a, b, br;
int main(){
	cin >> a >> b;
	n = (int)a.size(); m = (int)b.size();
	br = b;
	reverse(br.begin(), br.end());

	int ans = 0, cuta, cutb;
	for(int cas = 1; cas <= 2; cas++){
		for(int i = 0; i < n; i++){	// reverse before i
			string s1 = a.substr(i, n - i), s2 = a.substr(0, i);
			vector<int> l, r;
			l = kmp(s1, b);

			reverse(s2.begin(), s2.end());
			r = kmp(s2, br);
			reverse(r.begin(), r.end());

			if(chkmax(ans, r[0]))
				cuta = i - r[0], cutb = (cas == 1 ? 0 : m - r[0]);
			if(chkmax(ans, l[m - 1]))
				cuta = i, cutb = (cas == 1 ? m - l[m - 1] : 0);
			for(int j = 0; j < m - 1; j++)
				if(chkmax(ans, l[j] + r[j + 1]))
					cuta = i - r[j + 1], cutb = (cas == 1? j - l[j] + 1: m - j - r[j + 1] - 1);
		}
		swap(b, br);
	}

	cout << ans << endl;
	cout << cuta << " " << cutb << endl;
}

Compilation message (stderr)

necklace.cpp: In function 'int main()':
necklace.cpp:62:25: warning: 'cutb' may be used uninitialized in this function [-Wmaybe-uninitialized]
   62 |  cout << cuta << " " << cutb << endl;
      |                         ^~~~
necklace.cpp:62:18: warning: 'cuta' may be used uninitialized in this function [-Wmaybe-uninitialized]
   62 |  cout << cuta << " " << cutb << endl;
      |                  ^~~

• Subtask 1: 15 / 15