# Decide whether two strings $x, y$ can be split into substrings $a,b,c$ such that $x=abc$ and $y=cba$ What is the fastest algorithm for the following problem?

Given two strings $$x, y \in \Sigma^*$$ as input, decide whether there exists strings $$a, b, c \in \Sigma^*$$, such that $$x=abc$$ and $$y=cba$$.

By calculating all the length of the longest common prefix of $$s = x y$$ and all suffixes of $$s$$, we can compute all candidates for $$a$$ in $$O(n)$$ time.

For each candidate of $$a$$ with length $$k$$, we now just need to check whether $$x_k, x_{k + 1}, \ldots, x_{n}$$ is a rotation of $$y_0, y_1, \ldots, y_{n – k}$$. This can of course be done in $$O(n)$$.

However checking the rotations naively results in a worst-case $$O(n^2)$$ algorithm.

It seems that using the result from either https://arxiv.org/pdf/1601.08051.pdf or https://arxiv.org/pdf/1311.6235.pdf would make the algorithm run in expected $$O(n)$$ time.

Is there a simpler way of speeding up the rotation checking, where it is still faster than $$O(n^2)$$? Is there a way of making it deterministic, so that it still runs in $$O(n)$$ time? Posted on Categories proxies