Witam,

Natknąłem się na pewien problem przy wymyślaniu jednego algorytmu.
Męczę się już z tydzień i nie przychodzi mi do głowy żadne efektywne rozwiązanie mojego problemu.

Danych jest n ciągów liczbowych a. Problem polega na znalezieniu dla każdego ciągu a(i) ciągu a(j) gdzie i != j. i j Ciągi a(i) i a(j) muszą mieć możliwie najwięcej wspólnych elementów.
Np.:
a : 1, 2, 3, 2, 5, 8
b : 2, 3, 3, 5, 11
Dla tych dwóch ciągów wspólnych elementów jest 3 : 2, 3, 5.
Być może w jakiś sposób pomocna jest informacja, że ciągi wejściowe
są posortowane niemalejąco.

Zliczanie naiwne zajmuje złożoność O(n^2), ale być może istnieje jakiś szybszy sposób ? Może ktoś pomóc ?

Pozdrawiam.