Les plus longues substrations de longueur commune avec la même parité

Question

Étant donné deux séquences $ a $ et $ b $, trouver le plus grand $ x $ tel que dans $ a $ il y a une sous-chaîne $ A $ et substrat $ B $ dans $ b $ RÉCONTRE DE CES CONDITIONS:

1. longueur des deux $ A $ et $ B $ est égal à $ x $;
2. somme d'éléments dans $ A $ a la même parité que la somme des éléments en $ B $.

Durée $ a $ et $ b $ sont jusqu'à 5 $ Times10 ^ 5 $, si simple $ O (n ^ 2) $ La solution ne fera pas l'affaire.

Exemple:
$ a = [0, 1, 2, 3, 4, 5] $
$ b = [3, 1, 3, 6] $
Réponse: 3 (L'une des solutions possibles est $ A = [2, 3, 4], b = [3, 1, 3] $).

J'y ai réfléchi pendant des heures et je ne trouve pas de solution. Comment faire cela dans la complexité temporelle linéaire ou linéarithmique?

Je suis sûr que le problème peut être simplifié pour l'index $ i $, ne stockant que la somme d'éléments jusqu'à $ i $ modulo $2$. Cependant, cela ne m'aide pas beaucoup.

(Le problème vient d'un livre israélien plutôt vieux תכנות תחרותי: סביב אתגרים ('Prochatming compétitif') de Mordechai Ben-Ari. Le livre n'est pas bien connu et je n'ai pas trouvé de solution en hébreu, alors j'ai traduit le Problème en anglais pour une meilleure chance d'obtenir une réponse.)

Toute aide serait appréciée.