Submission #471056

#	Time	Username	Problem	Language	Result	Execution time	Memory
471056		KhaledFarhat	Necklace (Subtask 4) (BOI19_necklace4)	C++14	0 / 15	1596 ms	332 KiB

necklace

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

#define		F	first
#define		S	second
typedef pair<int, int>	pi;

class KmpSolver {
public:
    vector<int> getPrefixFunction(const string& s) { // tested
        vector<int> pi(s.size());

        for (int i = 1; i < s.size(); ++i) {
            for (int j = pi[i - 1]; j > 0; j = pi[j - 1]) {
                if (s[i] == s[j]) {
                    pi[i] = j + 1;
                    break;
                }
            }

            if (pi[i] == 0 && s[i] == s[0]) {
                pi[i] = 1;
            }
        }

        return pi;
	}
};

pair<int, pi> Solve(string s, string t, bool wasSReversed) {
	int n = s.size();
	int m = t.size();
	KmpSolver solver;
	pair<int, pi> answer;
	
	for (int firstPartInS = 0; firstPartInS <= n; ++firstPartInS) {
		string sPrefix = s.substr(0, firstPartInS);
		string sSuffix = s.substr(firstPartInS);
		
		reverse(sPrefix.begin(), sPrefix.end());
		
		for (int firstPartInT = 0; firstPartInT <= m; ++firstPartInT) {
			string tPrefix = t.substr(0, firstPartInT);
			string tSuffix = t.substr(firstPartInT);
			
			reverse(tSuffix.begin(), tSuffix.end());
			
			string firstText = sPrefix + "#" + tSuffix;
			int firstPartLength = solver.getPrefixFunction(firstText).back();
			int indexInS = firstPartInS - firstPartLength;
			
			string secondText = sSuffix + "#" + tPrefix;
			int secondPartLength = solver.getPrefixFunction(secondText).back();
			int indexInT = firstPartInT - secondPartLength;
			
			if (wasSReversed == true) {
				indexInS = firstPartInS + secondPartLength - 1;
				indexInS = (n - 1 - indexInS);
			}
			
			pair<int, pi> can;
			
			can.F = firstPartLength + secondPartLength;
			can.S.F = indexInS;
			can.S.S = indexInT;
			
			answer = max(answer, can);
		}
	}
	
	return answer;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	
	string s, t;
	cin >> s >> t;
	
	pair<int, pi> answer = Solve(s, t, false);
	
	reverse(s.begin(), s.end());
	answer = max(answer, Solve(s, t, true));
	
	cout << answer.F << "\n"
		<< answer.S.F << " " << answer.S.S;
	
	return 0;
}

Compilation message (stderr)

necklace.cpp: In member function 'std::vector<int> KmpSolver::getPrefixFunction(const string&)':
necklace.cpp:13:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   13 |         for (int i = 1; i < s.size(); ++i) {
      |                         ~~^~~~~~~~~~

• Subtask 1: 0 / 15