Najdłuższy powtarzający się podnapis

Zadanie 6 z 9 · rozdział 25Trudność: 3 z 3stringsubstringsdp

Treść zadania

Otrzymujesz napis. Znajdź najdłuższy podnapis, który występuje w nim co najmniej dwa razy. Wystąpienia mogą na siebie nachodzić — na przykład w napisie aaaa podnapis aaa występuje dwa razy (od indeksu 0 i od indeksu 1).

  • Jeśli kilka różnych podnapisów ma tę samą, maksymalną długość — wypisz ten, którego pierwsze wystąpienie zaczyna się najwcześniej.
  • Jeśli żaden znak się nie powtarza (nie ma powtarzającego się podnapisu) — wypisz pustą linię.

Dane wejściowe

Jedna linia: napis S.

Dane wyjściowe

Jedna linia: najdłuższy powtarzający się podnapis albo pusta linia.

Ograniczenia

  • 1 ≤ |S| ≤ 1000

Uwagi

  • Programowanie dynamiczne: niech w[i][j] (dla i < j) oznacza długość najdłuższego wspólnego początku fragmentów S[i:] i S[j:]. Jeśli S[i] == S[j], to w[i][j] = w[i + 1][j + 1] + 1, w przeciwnym razie 0. Wynikiem jest największa wartość w tablicy. Jeśli przeglądasz pary (i, j) w kolejności rosnącego i i zmieniasz wynik tylko na ściśle dłuższy, remisy rozstrzygną się same. Czas $O(n^2)$.
  • Sprawdzanie każdego podnapisu (jest ich około $n^2/2$) z osobnym wyszukiwaniem w całym napisie daje czas $O(n^3)$ — przy długich napisach to za dużo.

Przykłady

Wejście
pythonpython
Wyjście
python
Wejście
cdabxabycd
Wyjście
cd

Podnapisy cd i ab powtarzają się i oba mają długość 2, ale cd występuje po raz pierwszy wcześniej (od indeksu 0), a ab — dopiero od indeksu 2.

Potrzebujesz teorii?

Zasady obowiązujące w rozdziale 25

Trudniejsze zadania na napisach: samodzielna zamiana i usuwanie fragmentów, przedrostki, kodowanie RLE, rotacje, szukanie najdłuższych powtórzeń i wspólnych fragmentów (programowanie dynamiczne) oraz sprawdzanie nawiasów za pomocą stosu. Spróbuj rozwiązywać je własnymi pętlami, bez gotowych metod w rodzaju replace czy startswith — właśnie o to w nich chodzi.

Konwencje wspólne:

  • Każde zadanie to osobny program: czyta standardowe wejście i wypisuje wynik na standardowe wyjście.
  • Program nie wypisuje komunikatów typu „Podaj napis:”. Tekst podany w input("…") jest ignorowany przez sprawdzarkę.
  • Każdy napis zajmuje jedną całą linię wejścia, razem ze spacjami — wczytuj go przez input(), bez strip() i split().
  • Wielkość liter ma znaczenie (A i a to różne znaki), a spacja też jest znakiem.
  • Podnapis to ciągły fragment napisu, np. kot jest podnapisem kotlet, a ket — nie.
  • Pozycje znaków (indeksy) liczymy od 0, tak jak w Pythonie.
  • Odpowiedzi logiczne wypisuj jako Prawda albo Fałsz (o ile zadanie nie mówi inaczej).

Zadanie pochodzi z otwartego zbioru Nauka-Programowania (z rozwiązaniami wzorcowymi). Zgłoś błąd w treści lub testach.

Python uruchomi się w przeglądarce przy pierwszym teście.

Kod zapisuje się automatycznie w tej przeglądarce. Tab wstawia wcięcie; aby opuścić edytor klawiaturą, naciśnij Esc, a potem Tab.

Testy

Program dostaje „Wejście” przez input() i musi wypisać „Oczekiwane wyjście”. Liczby porównywane są z tolerancją 0,01, a tekst podany w input("…") nie jest sprawdzany.

Test 1

Nie uruchomiono
Wejście
abcdef
Oczekiwane wyjście
(brak)

Test 2

Nie uruchomiono
Wejście
aaaa
Oczekiwane wyjście
aaa

Test 3

Nie uruchomiono
Wejście
abcabcabc
Oczekiwane wyjście
abcabc

Test 4

Nie uruchomiono
Wejście
98432934021742343230
Oczekiwane wyjście
432

Test 5

Nie uruchomiono
Wejście
Arnold i Arnold
Oczekiwane wyjście
Arnold

Test 6

Nie uruchomiono
Wejście
efcdcdef
Oczekiwane wyjście
ef

Test 7

Nie uruchomiono
Wejście
x
Oczekiwane wyjście
(brak)

Test 8

Nie uruchomiono
Wejście
aa
Oczekiwane wyjście
a

Test 9

Nie uruchomiono
Wejście
bbbbbbabbbbbbaabbbabaabaaababbabaaabbaababbbbbabbabbaababbbaabbbbaababbaababbbabaaabbbaaaabbaabaababbbaaaababaabbaabaabbabbbbaabaabaabbabaabbaaabbbbbbaaabaabaaababaaaaaabbbabaabbababbbbaaaababaabaabaaaaabaaabbbbbbbbabbbaaaaabababbaaabbaaababaaaaabbbbabbbabbababbbbbaabbabaabaaabbabaaababaaaabbabaababaabbbbbaababbaaaaaabaabaaabaaaaababbabababaaaabababbaabbaababaaabaaaabbbabbbbbaaabbbbaaaaaababaaaabbbabaabbabbaabbbabaabaaaaaabaabbaabbbbbaaababbaaabbaaabbbaabaabbaabababbbabbbaaabbaaaababbaababbbbbabbaabbbabbabbaaaabbaaabbbbbaaabbabbaababaaaaaaaaabababaaabaaaaabaaaabaaabaaaaaaabbabbaababbababbabbbbabbbbabaabaaaaaababbababaabbbaaabbbbabbbbaaabaaaaababbbaababaaaabaaabbbbbbbaaaaaabbbababbbabababbabb
Oczekiwane wyjście
abbaababbbbbabba
Uruchom z własnymi danymi