Biorąc pod uwagę słowa, przekształcić go w palindrom z minimalnym dodatkiem liter do niego

Question

Oto bardzo interesujący wywiad pytanie:

Biorąc słowo, dołącz najmniejszą liczbę listów do niego, aby przekształcić go w palindrom.

Na przykład, jeśli "hello" jest podanym łańcuchem, wynik powinien brzmieć "hellolleh". Jeśli podano "coco", wynikiem powinno być "cococ".

Jednym podejściem, które przychodzi mi do głowy, jest dołączenie rewersu ciągu do końca oryginalnego łańcucha, a następnie spróbuj wyeliminować dodatkowe znaki z końca. Jednak nie mogę wymyślić, jak to zrobić skutecznie. Czy ktoś ma jakieś pomysły?

Answer 1

Najpierw należy wykonać funkcję testowania ciągu dla palindromu, pamiętając, że "a" i "aa" to palindromy. To są palindromy, prawda?

Jeśli wejście jest palindromem, zwróć (0 znaków należy dodać) Pętla od x [długość] do x [1] sprawdzanie, czy podzbiór ciągu x [i] .. x [długość ] jest palindromem, aby znaleźć najdłuższy palindrom.

Przenieś podciąg z łańcucha wejściowego przed najdłuższym palindromem, cofając go i dodając go do końca, powinien utworzyć najkrótszy palindrom przez dołączenie.

coco => c + oco => c + OCO + c

mmmeep => mmmee + p => mmmee + p + eemmm

Answer 2

Okay! Oto moja druga próba.

Chodzi o to, że chcemy sprawdzić, ile znaków na końcu ciągu może zostać ponownie wykorzystanych podczas dołączania dodatkowych znaków w celu uzupełnienia palindromu. W tym celu użyjemy modyfikacji algorytmu dopasowywania ciągów KMP. Używając KMP, szukamy oryginalnego łańcucha dla jego odwrotności. Gdy dojdziemy do samego końca ciągu, będziemy mieli jak najwięcej dopasowania między odwrotnością łańcucha a oryginalnym łańcuchem występującym na końcu łańcucha. Na przykład:

HELLO 
    O 

1010 
010 

3202 
202 

1001 
1001 

W tym miejscu KMP zwykle mówi "brak zgodności", chyba że oryginalny ciąg był palindromem. Ponieważ jednak wiemy, jaka część wstecznego ciągu została dopasowana, możemy zamiast tego po prostu dowiedzieć się, ile jeszcze znaków brakuje, a następnie dodać je na końcu łańcucha. W pierwszym przypadku brakuje nam LLEH. W drugim przypadku brakuje nam 1. W trzecim brakuje nam 3. W ostatnim przypadku niczego nam nie brakuje, ponieważ początkowy łańcuch to palindrom.

Środowisko wykonawcze tego algorytmu jest środowiskiem wykonawczym standardowego wyszukiwania KMP oraz czasem wymaganym do odwrócenia ciągu znaków: O (n) + O (n) = O (n).

Więc teraz argumentować poprawności. Będzie to wymagało pewnego wysiłku. Rozważmy optymalną odpowiedź:

| original string | | extra characters | 

Załóżmy, że czytasz ten tył od końca, co oznacza, że ​​będziemy czytać przynajmniej rewersie oryginalnego łańcucha. Część tego odwróconego sznurka rozciąga się wstecz w ciele pierwotnego łańcucha. W rzeczywistości, aby zminimalizować liczbę dodawanych znaków, musi to być jak największa liczba znaków, która kończy się powrotem do samego ciągu. Możemy to zobaczyć tutaj:

| original string | | extra characters | 
      | overlap | 

Co się dzieje w naszym kroku KMP? Cóż, kiedy szukasz odwrotności łańcucha wewnątrz samego siebie, KMP będzie utrzymywał tak długo jak tylko będzie to możliwe przez cały czas, ponieważ działa przez cały łańcuch. Oznacza to, że kiedy KMP trafi na koniec ciągu, dopasowana część, którą zachowa, będzie najdłuższym możliwym meczem, ponieważ KMP przenosi tylko punkt początkowy kandydującego meczu do przodu w przypadku niepowodzenia. W związku z tym mamy najdłuższe możliwe nakładanie się, więc otrzymamy możliwie najkrótszą liczbę znaków na końcu.

Nie jestem w 100% pewna, że ​​to działa, ale wygląda na to, że działa to w każdym przypadku, w którym mogę na nie rzucić. Dowód poprawności wydaje się rozsądny, ale jest trochę niezręczny, ponieważ formalny dowód oparty na KMP prawdopodobnie byłby nieco trudny.

Mam nadzieję, że to pomoże!

Answer 3

Aby odpowiedzieć wziąłbym to naiwne podejście:

1. kiedy potrzebujemy 0 znaków? kiedy string jest palindromem
2. kiedy potrzebujemy 1 znaku? jeśli oprócz pierwszego ciągu znaków jest palindromem
3. , gdy potrzebujemy 2 znaków? gdy oprócz znaków 2 uruchomić ciąg jest palindrom
4. etc etc ...

Zatem algorytm może być

for index from 1 to length 
    if string.right(index) is palindrome 
    return string + reverse(string.left(index)) 
    end 
    next 

edit

Nie jestem dużo Python, ale prosta realizacja powyższego pseudokodu może być

>>> def rev(s): return s[::-1] 
... 
>>> def pal(s): return s==rev(s) 
... 
>>> def mpal(s): 
... for i in range(0,len(s)): 
... if pal(s[i:]): return s+rev(s[:i]) 
... 
>>> mpal("cdefedcba") 
'cdefedcbabcdefedc' 
>>> pal(mpal("cdefedcba")) 
True 

Answer 4

Proste liniowe rozwiązanie czasu.

Zawołajmy naszego ciąg S.

Niech f (x, p) oznacza długość najdłuższego wspólnego przedrostka X i P. Oblicz f (S [0], rev (S)), F (S [1], rev (S)), ... gdzie S [k] jest sufiksem S rozpoczynającym się od pozycji k. Oczywiście, chcesz wybrać minimum k takie, że k + f (S [k], rev (S)) = len (S). Oznacza to, że musisz po prostu dodać k znaków na końcu. Jeśli k wynosi 0, żądło jest już palindromem. Jeśli k = len (S), to musisz dołączyć cały rewers.

Musimy szybko obliczyć f (S [i], P) dla wszystkich S [i]. To trudna część. Utwórz drzewo przyrostków S. Przechodzimy przez drzewo i aktualizujemy każdy węzeł o długość najdłuższego wspólnego przedrostka o P. Wartości na liściach odpowiadają f (S [i], P).