[Algorytmika]najmniejsze słowo zawierające dwa słowa

[leg14]

Mamy dane dwa słowa -\(\displaystyle{ u,v}\)- nad alfabetem \(\displaystyle{ \left\{ a,b\right\}}\) tej samej długości. Chcemy znaleźć najkrótsze słowo \(\displaystyle{ w}\) takie, że \(\displaystyle{ a,b}\) się w nim zawierają.
jasne jest, że to słowo będzie postaci \(\displaystyle{ u \cdot y = x \cdot v}\) lub \(\displaystyle{ x \cdot u = v \cdot y}\) gdzie \(\displaystyle{ x,y}\) to jakieś słowa tej samej długości (w najbardziej beznadziejnym przypadku będzie \(\displaystyle{ x = u,y=v}\) ).
Pytanie jak to zaimplementować, żeby było szybko? Jedyne rozwiązanie, jakie mi przychodzi do głowy, to oczywiście chamskie \(\displaystyle{ O(n^2)}\) .

[bartek118]

Najpierw trzeba sprawdzić, czy jedno słowo nie siedzi już w drugim. Jeśli nie, to może jakby znaleźć najdłuższy wspólny prefiks \(\displaystyle{ u}\) i sufiks \(\displaystyle{ v}\) (a potem odwrotnie) i tak je skleić?