Wpis z mikrobloga

Ma ktoś pomysł w jak rozwiązać zadanie: http://main.edu.pl/pl/archive/oi/19/lit
tak aby dla tych danych: https://ufile.io/8hp46 lub https://ufile.io/athxu (dwa stringi po 1 000 000 znaków)
czas wykonywania był poniżej 20 sekund ?

Mój kod: https://paste.ofcode.org/ivgy76j8xWBS6HTYuau74Y

Dla pierwszego zestawu danych wejściowych wykonuje się ok. 40 sek, dla drugiego prawie 4 minuty
#programowanie #python
  • 5
  • Odpowiedz
  • Otrzymuj powiadomienia
    o nowych komentarzach

"ile co najmniej zamian sąsiednich liter trzeba wykonać"


@Vetinari: jeśli dobrze zrozumiałem to result jest powiększany o ilość potrzebnych przesunięć pierwszej litery pierwszego nazwiska aby znalazła się ona na miejscu w jakim tkwi w drugim nazwisku, więc tak, kolega zamienia sąsiednie litery, tyle że w jednym kroku na raz.

no może powinno tam
  • Odpowiedz