-
Dana jest lista elementów.
Wyznacz wszystkie nietrywialne rotacje cykliczne danej listy, które dają w wyniku ją samą.
-
Dane są dwa napisy (w postaci tablic znaków) x i y.
Napisz procedurę szukaj : char array → char array → int, która znajduje najdłuższy
spójny fragment w napisie x, który jest prefiksem (fragmentem początkowym) napisu y.
Wynikiem procedury powinna być jego długość.
-
Okresem ciągu \([x_1; x_2; \dots; x_n]\) nazwiemy najmniejszą dodatnią liczbę całkowitą k,
taką że \(x_i = x_{i+k}\), dla \(i=1, 2, \dots, n-k\).
Napisz procedurę okresy: int list → int list, której wynikiem dla danej listy \([x_1; x_2; \dots; x_n]\)
jest taka lista \([y_1; y_2; \dots; y_n]\), że \(y_i\) jest okresem \([x_i; x_{i+1}; \dots; x_n]\).
-
Niech \((x_1, x_2, \dots, x_n)\) będzie danym niepustym ciągiem liczb.
Okresem całkowitym tego ciągu nazwiemy najmniejszą taką liczbę k, że:
- \(1 \le k \le n\),
- k jest dzielnikiem n,
- \(x_i = x_{i+k}\) dla wszystkich \(i = 1, \dots n-k\).
Zauważmy, że każdy ciąg ma okres całkowity, co najwyżej jest to \(k=n\).
Na przykład, okresem całkowitym ciągu \([1;3;2;1;1;3;2;1;1;3;2;1]\) jest 4, a okresem całkowitym ciągu \([1;3;2;1;1]\) jest 5.
Napisz procedurę okres : int array → int, która dla danego ciągu wyznaczy jego okres całkowity.
-
Dana jest tablica \(a\) zawierająca ciąg \(n\) elementów.
Napisz procedurę \(\mathtt{presuf}: \alpha\ \mathtt{array} \to \mathtt{int}\),
która dla danej tablicy \(a\) znajduje długość najdłuższego jej prefikso-sufiksu,
który ma przynajmniej trzy rozłączne wystąpienia w \(a\).
-
Dana jest tablica \(a\) zawierająca ciąg \(n\) elementów.
Napisz procedurę \(\mathtt{double}: \alpha\ \mathtt{array} \to \mathtt{int}\),
która dla danej tablicy \(a\) znajduje długość \(i\) najdłuższego jej prefiksu, który powtórzony dwukrotnie nadal jest jej prefiksem,
tzn.\ \(a.(0) = a.(i)\), \(a.(1) = a.(i+1)\), ..., \(a.(i-1) = a.(2i-1)\).
- [XII OI, zadanie Szablon]
Chcemy wykonać długi napis.
W tym celu najpierw przygotowujemy odpowiedni szablon z wyciętymi literkami.
Następnie taki szablon można przyłożyć we właściwym miejscu do ściany i malujemy po nim farbą.
Malujemy zawsze po całym szablonie, ale dopuszczamy, aby litery były malowane wielokrotnie.
Literki na szablonie znajdują się koło siebie (nie ma tam przerw).
Zadanie polega na wyznaczeniu minimalnej długości szablonu, za pomocą którego można wykonać cały napis.
- [XIII OI, zadanie Okresy słów]
Napis Q jest okresem A, jeśli Q jest prefiksem właściwym A oraz A
jest prefiksem (niekoniecznie właściwym) napisu QQ.
Przykładowo, napisy abab i ababab są okresami napisu abababa.
Maksymalnym okresem napisu A nazywamy najdłuższy z jego okresów, lub napis pusty, jeśli A nie posiada okresu.
Dla przykładu, maksymalnym okresem napisu ababab jest abab.
Maksymalnym okresem abc jest napis pusty.
Napisz procedurę, która dla danego (w postaci listy) napisu obliczy listę długości maksymalnych
okresów kolejnych jego prefiksów.
-
Dana jest tablica \(a\) zawierająca \(n\) znaków.
Rotacją cykliczną takiej tablicy o \(i\) (dla \(0 \le i < n\)) nazwiemy tablicę powstałą z przeniesienia elementów
\(a.(0), \dots, a.(i-1)\) z początku tablicy na jej koniec, przy równoczesnym przesunięciu elementów \(a.(i),\dots, a.(n-1)\) o \(i\) pozycji w lewo.
Napisz procedurę \(\mathtt{minrot}: \mathtt{char~array} \to \mathtt{int}\),
która dla danej tablicy znaków \(a\) zwróci taką liczbę \(i\), że rotacja tablicy \(a\) o \(i\) pozycji jest najmniejsza w porządku leksykograficznym,
spośród wszystkich jej rotacji cyklicznych.
-
Dane są dwa napisy (w postaci tablic znaków) \(x\) i \(y\).
Napisz procedurę \(\mathtt{szukaj}:\mathtt{char~array}\to\mathtt{char~array}\to\mathtt{int}*\mathtt{int}\),
która znajduje najdłuższy spójny fragment występujący w obu napisach.
Wynikiem procedury powinna być para: pozycje jego początków w obu napisach.
-
Dany jest tekst w postaci tablicy znaków \([|c_1;\dots;c_n|]\).
Napisz procedurę podsłowo : char array → (int * int),
która znajduje takie pozycje w tekście \((i,j)\), że:
- \(0 < i \le j \le n\),
-
liczba wystąpień \(k\) napisu \([|c_i;\dots;c_j|]\) w danym tekście, pomnożona przez jego długość
(czyli \(k \cdot (j-i+1)\)) jest maksymalna.
Dla pustej tablicy poprawnym wynikiem jest (0,0).