Zadanie 2. Najdłuższy spójny podciąg palindromiczny

Spójny podciąg to taki, którego każde dwa sąsiednie wyrazy były sąsiednimi wyrazami pierwotnego ciągu. Natomiast spójny podciąg palindromiczny to taki podciąg, który czytany w obu kierunkach (czyli od lewej do prawej, jak i wspak) jest identyczny.

W pliku napisy.txt znajduje się 100 ciągów znaków oddzielonych znakiem nowej linii.

Przykładowe dane:

• ySSyQTffTQcEWWEc

• ZBdUUdBZzPPz

• VbbV

Napisz program znajdujący najdłuższy spójny podciąg palindromiczny danego ciągu znaków. Wykorzystaj programowanie dynamiczne.

Specyfikacja problemu:

Dane:

• n – długość wejściowego ciągu znaków; liczba naturalna

• S[] – ciąg znaków, w którym należy znaleźć najdłuższy podciąg palindromiczny

Wynik:

• najdluzszy_palindrom – znaleziony najdłuższy podciąg palindromiczny; ciąg znaków

Użyj napisanego programu do znalezienia najdłuższych podciągów palindormicznych dla każdego z ciągów znaków w pliku napisy.txt. Wyniki zapisz do pliku palindromy.txt, każdy w osobnej linii.

1.

Jedno z bezpośrednich rozwiązań polegałoby na sprawdzeniu każdego spójnego podciągu. Niech n będzie długością wejściowego ciągu znaków. Wszystkich takich spójnych podciągów jest wtedy O(nIndeks górny 2 Indeks górny koniec2). Sprawdzenie czy ciąg długości n jest palindromiczny zajmuje O(n) czasu. Tak określony prosty algorytm siłowy działa w czasie O(nIndeks górny 3 Indeks górny koniec3) . Szybsze rozwiązanie działające w czasie O(nIndeks górny 2 Indeks górny koniec2) może opierać się na programowaniu dynamicznym

2. 

Niech d będzie tablicą dwuwymiarową rozmiaru n x n. Wyraz d[i][j] jest równy 1, jeśli spójny podciąg pomiędzy indeksami i oraz j jest palindromiczny.

Np. dla wyrazu „1abdedba254” podciąg „bdedb” jest palindromiczny, zatem wyraz d[2][6]musi być równy 1. Tak samo d[3][5] („ded”) i d[1][7] („abdedba”) też będą równe 1. Z drugiej strony podciąg „1abdedb” nie jest palindromiczny, więc podciąg d[0][6] jest równy 0.

3.

Zapisanie pseudokodu rozpoczniemy od zdefiniowania nagłówka funkcji będącej implementacją algorytmu. Jako argument wymagany jest tylko ciąg znaków S i długość ciągu n.

funkcja najdluzszySpojnyPalindrom(S[], n):

4.

Następnie zdefiniujemy dwuwymiarową tablicę d o rozmiarze n x n, którą wypełniamy 0. Będziemy wypełniać wyłącznie jej część ponad przekątną. Łatwo zauważyć, że d[i][j] będzie zawsze równe d[j][i], więc nie ma potrzeby wypełniać całej tablicy. Dodatkowo określimy zmienną maks_dlugosc przechowującą dotychczas największą długość palindromicznego spójnego podciągu.

funkcja najdluzszySpojnyPalindrom(S[], n):
	d[n][n] ← tablica n x n, wypełniona 0
	maks_dlugosc ← 1

5.

Na początku wypełniamy przekątną tablicy d[]. Pojedynczy znak jest zawsze palindromem, dlatego wszystkie pola d[i][i] dla 0 < = i < n powinny mieć wartość 1.

funkcja najdluzszySpojnyPalindrom(S[], n):
	d[n][n] ← tablica n x n, wypełniona 0
	maks_dlugosc ← 1

	dla i = 0, 1, ... , n - 1 wykonuj:
		d[i][i] ← 1

6.

Następnie zdefiniujemy zmienną pomocniczą start, która będzie przechowywać indeks, od którego rozpoczyna się najdłuższy znaleziony podciąg palindromiczny. W pojedynczej pętli, iterując po ciągu S, będziemy poszukiwać palindromów długości 2.Znajdując taki palindrom pomiędzy S[i]oraz S[i + 1] zapiszemy w d[i][i+1] wartość 1.

funkcja najdluzszySpojnyPalindrom(S[], n):
	d[n][n] ← tablica n x n, wypełniona 0
	maks_dlugosc ← 1

	dla i = 0, 1, ... , n - 1 wykonuj:
		d[i][i] ← 1

	start ← 0
	dla i = 0, 1, ..., n - 1 wykonuj:
		jeżeli S[i] = S[i + 1]:
			d[i][i + 1] ← 1
			start ← i
			maks_dlugosc ← 2

7.

Kolejnym krokiem jest utworzenie dwóch zagnieżdżonych pętli, które pozwolą nam wypełnić pozostałe pola w tablicy d[]. Zmienna i będzie wskazywała na początek sprawdzonego podciągu, zmienna k będzie określała jego długość natomiast zmienna j będzie zmienną pomocniczą, której przypiszemy końcowy indeks sprawdzanego podciągu.

funkcja najdluzszySpojnyPalindrom(S[], n):
	d[n][n] ← tablica n x n, wypełniona 0
	maks_dlugosc ← 1

	dla i = 0, 1, ... , n - 1 wykonuj:
		d[i][i] ← 1

	start ← 0
	dla i = 0, 1, ..., n - 1 wykonuj:
		jeżeli S[i] = S[i + 1]:
			d[i][i + 1] ← 1
			start ← i
			maks_dlugosc ← 2
	
	dla k = 3, 4, ..., n wykonuj:
		dla i = 0, 1, ..., n - k wykonuj:
			j ← i + k - 1

8.

W każdej iteracji pętli będziemy chcieli sprawdzić, czy podciąg pomiędzy indeksem i oraz j jest palindromem. Aby tak było, muszą być spełnione dwa warunki: podciąg pomiędzy i + 1 oraz j - 1 musi być palindromem oraz S[i]==S[j]. Jeżeli został znaleziony nowy palindrom musimy również sprawdzić, czy nie jest on nowym najdłuższym znalezionym rozwiązaniem. W takim wypadku ustawiamy zmienną start na indeks i natomiast maks_dlugosc na k.

funkcja najdluzszySpojnyPalindrom(S[], n):
	d[n][n] ← tablica n x n, wypełniona 0
	maks_dlugosc ← 1

	dla i = 0, 1, ... , n - 1 wykonuj:
		d[i][i] ← 1

	start ← 0
	dla i = 0, 1, ..., n - 1 wykonuj:
		jeżeli S[i] = S[i + 1]:
			d[i][i + 1] ← 1
			start ← i
			maks_dlugosc ← 2
	
	dla k = 3, 4, ..., n wykonuj:
		dla i = 0, 1, ..., n - k wykonuj:
			j ← i + k - 1

			jeżeli d[i + 1][j - 1] ORAZ S[i] = S[j]:
				d[i][j] ← 1

				jeżeli k > maks_dlugosc:
					start ← i
					maks_dlugosc ← k

9.

Na koniec definiujemy tablicę najdluzszy_palindrom[] o długości maks_dlugosc, która pozwoli nam zwrócić znalezione rozwiązanie. Zapiszemy do niej w pętli podciąg zaczynający się na indeksie start, a kończący na start + maks_dlugosc‑1, a następnie zwrócimy.

funkcja najdluzszySpojnyPalindrom(S[], n):
	d[n][n] ← tablica n x n, wypełniona 0
	maks_dlugosc ← 1

	dla i = 0, 1, ... , n - 1 wykonuj:
		d[i][i] ← 1

	start ← 0
	dla i = 0, 1, ..., n - 1 wykonuj:
		jeżeli S[i] = S[i + 1]:
			d[i][i + 1] ← 1
			start ← i
			maks_dlugosc ← 2
	
	dla k = 3, 4, ..., n wykonuj:
		dla i = 0, 1, ..., n - k wykonuj:
			j ← i + k - 1

			jeżeli d[i + 1][j - 1] ORAZ S[i] = S[j]:
				d[i][j] ← 1

				jeżeli k > maks_dlugosc:
					start ← i
					maks_dlugosc ← k
	
	najdluzszy_palindrom[maks_dlugosc] ← tablica znaków o rozmiarze maks_dlugosc
	dla i = 0, 1, ..., maks_dlugosc - 1 wykonuj:
		najdluzszy_palindrom[i] ← S[start + i]

	zwróć najdluzszy_palindrom

Odpowiedź do zadania

Odpowiedź dla danych z pliku napisy.txt znajduje się w załączniku: