Longest substrings of common length with the same parity

Question

Given two sequences $a$ and $b$, find largest $x$ such that in $a$ there is substring $A$ and substring $B$ in $b$ meeting those conditions:

1. length of both $A$ and $B$ is equal to $x$;
2. sum of elements in $A$ has the same parity as sum of elements in $B$.

Lengths of $a$ and $b$ are up to $5\times10^5$, so simple $O(n^2)$ solution won't do.

Example:
$a = [0, 1, 2, 3, 4, 5]$
$b = [3, 1, 3, 6]$
Answer: 3 (one of the possible solutions is $A = [2, 3, 4], B = [3, 1, 3]$).

I've thought about it for hours and can't find a solution. How to do this in linear or linearithmic time complexity?

I'm quite sure the problem can be simplified to for index $i$, storing only sum of elements up to $i$ modulo $2$. However, it doesn't help me much.

(The problem comes from a rather-old Israeli book תכנות תחרותי: סביב אתגרים ('Competetitive programming') by Mordechai Ben-Ari. The book isn't well known and I couldn't find any solution in Hebrew, so I translated the problem into English for a better chance of getting answer.)

Any help will be appreciated.