Submission #1314546

#TimeUsernameProblemLanguageResultExecution timeMemory
1314546Jawad_Akbar_JJNecklace (Subtask 1-3) (BOI19_necklace1)C++20
85 / 85
256 ms488 KiB
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

vector<int> KMP(string s, bool rev){
	if (rev)
		reverse(begin(s), end(s));

	int n = s.size();
	vector<int> kmp(n, 0);

	for (int i=1, z = 0;i<n;i++){
		if (s[z] == s[i])
			kmp[i] = ++z, kmp[i] *= s[i] != '#';
		else if (z == 0)
			continue;
		else
			z = kmp[z-1], i--;
	}
	if (rev)
		reverse(begin(kmp), end(kmp));
	return kmp;
}

pair<int, pair<int, int>> solve(string S, string T){
	int n = S.size(), m = T.size(), Ans = 0, i1, i2;
	for (int i=0;i<=n;i++){
		string s1, s2 = T;
		while (s2.size() + i < n + m + 1)
			s2 += '#';
		for (int j=0;j<n;j++){
			if (j < i)
				s2 += S[j];
			else
				s1 += S[j];
		}
		while (s1.size() < n + 1)
			s1 += '#';
		s1 += T;

		vector<int> v1 = KMP(s1, 0), v2 = KMP(s2, 1);
		
		for (int j=-1;j<m;j++){
			int b = v1[n + j + 1], a = v2[j + 1];
			if (a + b > Ans)
				Ans = a + b, i1 = i - a, i2 = j - b + 1;
		}
	}
	return {Ans, {i1, i2}};
}

int main(){
	string S, T;
	cin>>S>>T;

	pair<int, pair<int, int>> ans1 = solve(S, T);
	reverse(begin(T), end(T));
	pair<int, pair<int, int>> ans2 = solve(S, T);
	if (ans1.first >= ans2.first)
		cout<<ans1.first<<" "<<ans1.second.first<<" "<<ans1.second.second<<'\n';
	else
		cout<<ans2.first<<" "<<ans2.second.first<<" "<<T.size() - ans2.first - ans2.second.second<<'\n';
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...