# Problem 65: Longest Common-Parity Factors


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$.