Baltic OI 2019 - Necklace

Solution 1 (Magic DP)

Time complexity: $\mathcal O(N^2)$. Memory complexity: $\mathcal O(N)$.

Code

//DP: time O(n^2), mem O(n)
#include <algorithm>
#include <iostream>
#include <string>
#include <vector>

using namespace std;

int solve_noflip(string &s, string &t, int *loc) {
	int n = s.size();  // vertical

Solution 2 (KMP)

Time complexity: $\mathcal O(N^2)$. Memory complexity: $\mathcal O(N)$.

Let the two strings be $S$ and $T$, and their lengths be $N$ and $M$ respectively.

For simplicity, assume that we can't flip the necklace over. (To handle the case where we can, just reverse $T$, run our algorithm again, and take the best result.)

We essentially want to find two strings $A$ and $B$, and two indices $i$ and $j$ such that:

• $A$ is a suffix of $S[0 : i]$ and a prefix of $T[j + 1 : M - 1]$.
• $B$ is a prefix of $S[i + 1 : N - 1]$ and a suffix of $T[0 : j]$.
• $|A| + |B|$ is maximal.

We can thus test each $i$ to find the best $j$ for that $i$, and then take the best overall result.

To find the best $j$, we first reverse $T$ and split $S$ at index $i$. This turns the subproblem into finding the longest common prefix/suffix between two pairs of strings. This is a classical application of KMP, so we can solve this subproblem in $\mathcal O(N)$ time and $\mathcal O(N)$ memory.

Code

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

int p1[6002], p2[6002];

void fill_p(string s, int *p) {
	for (int i = 1; i < s.size(); i++) {
		int j = p[i - 1];
		while (j && s[i] != s[j]) j = p[j - 1];