Submission #471063

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
471063	2021-09-07T00:24:32 Z	KhaledFarhat	Necklace (Subtask 4) (BOI19_necklace4)	C++14	15 / 15	388 ms	532 KB

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;
	}
};

tuple<int, int, int> Solve(string s, string t, bool wasSReversed) {
	int n = s.size();
	int m = t.size();
	KmpSolver solver;
	tuple<int, int, int> answer;

	string reversedT = t;
	reverse(reversedT.begin(), reversedT.end());
	
	for (int firstPartInS = 0; firstPartInS <= n; ++firstPartInS) {
		string sPrefix = s.substr(0, firstPartInS);
		reverse(sPrefix.begin(), sPrefix.end());
		string firstText = sPrefix + "#" + reversedT;
		vector<int> firstPi = solver.getPrefixFunction(firstText);

		string sSuffix = s.substr(firstPartInS);				
		string secondText = sSuffix + "#" + t;
		vector<int> secondPi = solver.getPrefixFunction(secondText);
		
		for (int firstPartInT = 0; firstPartInT <= m; ++firstPartInT) {
			int firstPartLength = secondPi[(n - firstPartInS) + firstPartInT];
			int secondPartLength = firstPi[m - firstPartInT + firstPartInS];
			
			int indexInS = -1;
			
			if (wasSReversed == false) {
				indexInS = firstPartInS - secondPartLength;
			}
			else {
				indexInS = n - firstPartInS - firstPartLength;
			}
			
			int indexInT = firstPartInT - firstPartLength;
						
			answer = max(answer, make_tuple(firstPartLength + secondPartLength, indexInS, indexInT));
		}
	}
	
	return answer;
}

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

Compilation message

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

15.0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	342 ms	452 KB	Output is correct
2	Correct	296 ms	448 KB	Output is correct
3	Correct	388 ms	332 KB	Output is correct
4	Correct	302 ms	452 KB	Output is correct
5	Correct	191 ms	424 KB	Output is correct
6	Correct	211 ms	444 KB	Output is correct
7	Correct	258 ms	332 KB	Output is correct
8	Correct	297 ms	532 KB	Output is correct
9	Correct	313 ms	396 KB	Output is correct