Szablon Znalezc najkrotsze podslowo, ktorego wystapienia pokrywaja
zadany tekst (znalezc najkrotszy cover).
Duzo trudniejsze jest podobne zadanie znajdowania tzw. seed
(wystapienia moga wystawac poza tekst).
Pierwotek abstrakcyjny
Dany zbior slow dwuliterowych, znalezc
najkrotsze slowo zawierajace te slowa jako podslowa.
(NP-trudne dla 3-literowych).
Wirusy
Dla danego zbioru slow stwierdzic,
czy istnieje slowo nieskonczone, ktore nie
zawiera zadnego slowa z tego zbioru (jako podslowa).
Ciagi bez zajakniec
Znalezc slowo 3-literowe o zadanej dlugosci
niezawierajace podslow kwadratowych (a co z leksykograficznie
pierwszym?).
Powtorzenia Obliczyc najdluzsze wspolne podslowo dla danego zbioru slow
(na wejsciu sa slowa z tego zbioru).
Co bedzie, gdy zbior slow bedzie taki jak w zadaniu
``Wybory symetryczne''?
Palindromy
Zadany zbior X slow, kazde jest palindromem.
Ile jest palindromow w zbiorze X X?
Co jesli zbior X zawiera nie tylko palindromy?
Okresy slow
2-okres slowa v to okres wlasciwy o dlugosci co
najmniej v/2 lub slowo puste, jezeli taki nie istnieje.
Wyznaczyc maksymalne 2-okresy wszytkich
prefiksow danego slowa.
Rownanie na slowach
Dane rownanie na slowach i (ustalone) dlugosci zmiennych.
Obliczyc liczbe rozwiazan rownania nad alfabetem binarnym.
Wybory symetryczne
Ile jest palindromow w zbiorze slow
bedacym konkatenacja pewnej liczby zbiorow dwulementowych
(wejsciem sa slowa w zbiorach dwuelementowych.)
Ogolniej, zbior zadany wyrazeniem regularnym bez gwiazdki.
Naszyjniki
Dane dwa slowa w postaci skompresowanej RLE.
Stwierdzic czy sa cyklicznie rownowazne.
BBB
Zadane slowo nawiasowe postaci (^i S )^j.
Sprowadzic je do poprawnego wyrazenia nawiasowego za pomoca
zamian nawiasow w S na przeciwne (koszt x) i pojedynczych rotacji
cyklicznych S (koszt y) minimalnym kosztem.
Przyspieszanie algorytmu
Znalezc efektywny algorytm sprawdzania rownowaznosci
slow przy relacji x rownowazne xx.
Slowa
Zadane slowo z jako konkatenacja slow Fibonacciego
(wejsciem jest ciag indeksow). Stwierdzic czy
z jest podslowem jakiegos slowa Fibonacciego.
A jak wyznaczyc indeks pierwszego takiego slowa Fibonacciego?
Punkty (pozornie nietekstowe)
Czy zbior punktow P na plaszczyznie mozna przeksztalcic na
zbior Q za pomoca izometrii i jednokladnosci?
Slonie (pozornie nietekstowe)
Jaki jest minimalny sumaryczny koszt transpozycji
zmieniajacych jedna permutacje zbioru {1,2,...,n} w druga?
Koszt transpozycji to suma wag uczestniczacych w niej liter.
(NP-trudne dla permutacji multizbioru).
Pociagi
Dany ciag slow n-literowych i ciag zamian par liter w pewnych
parach tych slow. Dla kazdego elementu ciagu wyznaczyc, w ktorym
momencie w ciagu bylo najwiecej slow takich samych jak to slowo.
Osie symetrii (pozornie nietekstowe)
Wyznaczyc liczbe osi symetrii danego wielokata prostego.
Kod
Dany jest kod prefiksowy (drzewo binarne, ktorego liscie to
slowa kodowe, a kazdy wezel wewnetrzny ma stopien 2).
Slowo synchronizujace kodu to slowo kodowe s, takie ze dowolny
sufiks dowolnego napisu X zlozonego ze slow kodowych zawierajacy
s, poczawszy od s odkodowuje sie tak jak X.
Znalezc wszystkie slowa synchronizujace.
Slowa Fibonacciego
Ile razy dane slowo wystepuje (jako podslowo) w n-tym
slowie Fibonacciego.
Wyrownywanie slow
Dane dwa slowa x, y oraz zbior slow Z.
Dokleic do kazdego ze slow x, y jak najmniej slow z Z, tak
aby uzyskac to samo slowo.
(Jak sprawdzic, czy dany zbior slow jest kodem?)
Palindromy
Podzielic dane slowo na najmniejsza i najwieksza liczbe
palindromow parzystych.
Skladanie slow
Wyznaczyc liczbe podciagow danego ciagu slow, ktore
sklejaja sie do zadanego slowa.