Zadanie 3.3. (0-4)
Prefiksosufiksem pary słów s1, s2 nazywamy słowo, które jest początkiem s1 (czyli s1 zaczyna
się tym słowem) oraz końcem s2 (czyli s2 kończy się tym słowem) lub początkiem s2 oraz
końcem s1.
Podaj wszystkie pary słów z pliku pary.txt, dla których najdłuższy prefiksosufiks ma
co najmniej 5 liter. Dla każdej podanej w odpowiedzi pary słów podaj długość najdłuższego
prefiksosufiksu tej pary.
Przykłady:
Dla pary aabbbca caacaab mamy następujące prefiksosufiksy:
aab - początek pierwszego słowa i koniec drugiego
ca - początek drugiego słowa i koniec pierwszego.
Najdłuższy prefiksosufiks ma długość 3, zatem para tych słów nie spełnia wymaganych
warunków.
Dla pary abbaabaa baabaabba mamy następujące prefiksosufiksy:
a - początek pierwszego słowa i koniec drugiego
abba - początek pierwszego słowa i koniec drugiego
baa - początek drugiego słowa i koniec pierwszego
baabaa - początek drugiego słowa i koniec pierwszego.
Najdłuższy prefiksosufiks ma długość 6, zatem para spełnia warunki wymagane w zadaniu.
Dla pliku pary_przyklad.txt poprawną odpowiedzią jest
ececdddeed dddeedd 6
(najdłuższy prefiksosufiks ma długość 6)
Do oceny oddajesz:
• plik tekstowy wyniki3.txt zawierający odpowiedzi do zadań 3.1.-3.3. (odpowiedź do
każdego zadania powinna być poprzedzona jego numerem)
• plik(-i) zawierający(-e) kody źródłowe Twoich programów o nazwach odpowiednio
(uwaga: brak tych plików jest równoznaczny z brakiem rozwiązania zadania):
zadanie 3.1
zadanie 3.2
zadanie 3.3
3.3.
0-1-
2-3-4
MINP-R0_100
Zadanie 3.3. (0-4)
Wymaganie ogólne
Wymagania szczegółowe
II. Programowanie i rozwiązywanie
problemów z wykorzystaniem komputera
oraz innych urządzeń cyfrowych: układanie
i programowanie algorytmów,
organizowanie, wyszukiwanie
i udostępnianie informacji, posługiwanie się
aplikacjami komputerowymi.
Zdający:
P.II.1) projektuje i programuje rozwiązania
problemów z różnych dziedzin, stosuje przy
tym: instrukcje wejścia/wyjścia, wyrażenia
arytmetyczne i logiczne, instrukcje
warunkowe, instrukcje iteracyjne, funkcje
z parametrami i bez parametrów, testuje
poprawność programów dla różnych
danych;
Zasady oceniania rozwiązań zadań
w szczególności programuje algorytmy
z punktu I.2).
II.1) projektuje i tworzy rozbudowane
programy w procesie rozwiązywania
problemów, wykorzystuje w programach
dobrane do algorytmów struktury danych,
w tym struktury dynamiczne i korzysta
z dostępnych bibliotek dla tych struktur.
II.2) sprawnie posługuje się zintegrowanym
środowiskiem programistycznym przy
pisaniu, uruchamianiu i testowaniu
programów.
Zasady oceniania
4 pkt - odpowiedź poprawna, w tym:
3 pkt - pary słów
1 pkt - długości najdłuższych prefiksosufiksów.
3 pkt - podanie par słów, dla których najdłuższy prefiskosufiks ma:
więcej niż 5 liter
albo
co najmniej 4 litery,
oraz podanie dla każdej z tych par długości najdłuższego prefiksosufiksu.
2 pkt - podanie par słów oraz długości najdłuższych prefiksosufiksów (po jednym punkcie za
pary i za długości) w przypadku:
sprawdzania prefiksosufiksów tylko dla kolejności s1, s2 lub tylko dla kolejności s2, s1
albo
szukania najdłuższego prefiksosufiksu w pliku z danymi, wynik:
aababbbababbbbbbaab bbbbaabbababababa 7
albo
sprawdzania prefiksosufiksów o długości dokładnie 5.
0 pkt - odpowiedź niepoprawna albo brak odpowiedzi.
Poprawna odpowiedź
bbbbaabbababbaaaa baaaaabaaabbbabab 5
aababbbababbbbbbaab bbbbaabbababababa 7
aaaababaaaabbbb aabbbbbabbbaaaa 6
bbbbabaaabbbabb aaababaabbbbbbba 5
ccccabacbba acbbabcbcbcbaa 5
caabbccabccc cabccccabbaac 6
abaacabcccccabbbc abbbcbbbbbcabaca 5
Siedem par: `` bbbbaabbababbaaaa baaaaabaaabbbabab 5 aababbbababbbbbbaab bbbbaabbababababa 7 aaaababaaaabbbb aabbbbbabbbaaaa 6 bbbbabaaabbbabb aaababaabbbbbbba 5 ccccabacbba acbbabcbcbcbaa 5 caabbccabccc cabccccabbaac 6 abaacabcccccabbbc abbbcbbbbbcabaca 5 ``
Pary słów, dla których najdłuższy prefiksosufiks ma co najmniej 5 liter (para → długość najdłuższego prefiksosufiksu):
\n| Para słów | Długość |
| bbbbaabbababbaaaa baaaaabaaabbbabab | 5 |
| aababbbababbbbbbaab bbbbaabbababababa | 7 |
| aaaababaaaabbbb aabbbbbabbbaaaa | 6 |
| bbbbabaaabbbabb aaababaabbbbbbba | 5 |
| ccccabacbba acbbabcbcbcbaa | 5 |
| caabbccabccc cabccccabbaac | 6 |
| abaacabcccccabbbc abbbcbbbbbcabaca | 5 |
Prefiksosufiks pary $s_1, s_2$ to słowo będące jednocześnie:
\nDla każdej pary szukamy najdłuższego takiego słowa i wypisujemy pary, w których jego długość $\\ge 5$.
\nAlgorytm dla jednej pary (sprawdzamy obie „strony" i bierzemy dłuższy wynik):
\n```python
def najdluzszy_ps(a, b):
najlepszy = 0
maxk = min(len(a), len(b))
for k in range(1, maxk + 1):
if a[:k] == b[-k:]:
najlepszy = k
return najlepszy
def ps_pary(s1, s2):
return max(najdluzszy_ps(s1, s2), najdluzszy_ps(s2, s1))
with open('pary.txt') as f, open('wyniki3.txt', 'a') as w:
for line in f:
s1, s2 = line.split()
d = ps_pary(s1, s2)
if d >= 5:
w.write(f'{s1} {s2} {d}\\n')
Po przejrzeniu wszystkich 500 par pliku pary.txt warunek $\\ge 5$ spełnia siedem par wypisanych w tabeli powyżej. Zwróćmy uwagę, że dla każdej pary bierzemy najdłuższy prefiksosufiks (a nie pierwszy znaleziony), rozpatrując obie możliwe konfiguracje (prefiks $s_1$/sufiks $s_2$ oraz prefiks $s_2$/sufiks $s_1$) - np. dla pary aababbbababbbbbbaab bbbbaabbababababa najdłuższy prefiksosufiks ma długość 7.
aababbbababbbbbbaab bbbbaabbababababa 7).(Uwaga: brak odpowiedzi ze strony AI jest rozbieżny z kluczem.)
"}]}