CLR cover
Previous problem

Problem 65: Longest Common-Parity Factors

Next problem
\( \newcommand{\parity}{\mathit{parity}}% \newcommand{\PARITY}{\mathit{Parity}}% \newcommand{\lcpf}{\mathit{lcpf}}% \def\sa#1{\tt{#1}} \def\dd{\dot{}\dot{}} \)

For a word $v\in\{\sa{0},\sa{1}\}^+$ we denote by $\parity(v)$ the sum modulo 2 of letter $\sa{1}$ occurring in $v$. For two words $x,y\in\{\sa{0},\sa{1}\}^+$ we denote by $\lcpf(x,y)$, the longest common-parity factor, the maximal common length of two factors $u$ and $v$ of $x$ and $y$ respectively with $\parity(u)=\parity(v)$. Surprisingly this problem essentially amounts to computing all periods of words.

Show how to compute in linear time $\lcpf(x,y)$ for two binary words $x$ and $y$.