Wyszukiwanie wzorca w tekście

Zadanie AL13.1 Podaj wartości funkcji prefiksowej dla wzorca P = ababca. (Wartości funkcji prefiksowej można liczyć na podstawie definicji, niekoniecznie symulując algorytm Knutha-Morrisa-Pratta.

Z poniższych zadań 13.2 i 13.3 należy wybrać tylko jedno zadanie

Zadanie AL13.2 (3 pkt) Zmodyfikuj algorytm Knutha-Morrisa-Pratta tak, aby wyszukiwał w tekście T dany wzorzec P przy założeniu, że każdy znak zapytania ’?’ w tekście T może odpowiadać dowolnemu znakowi, a następnie zaimplementuj tę modyfikację.

Zadanie AL13.3 (5 pkt) Zaimplementuj algorytmy wyszukiwania wzorca w tekście modyfikując te algorytmy w taki sposób, żeby

• były pomijane znaki zmiany wiersza i w tekście i we wzorcu (bo wzorzec i pasujące fragment tekstu mogą być inaczej połamane na wiersze).
• miejsca wystąpienia wzorca w tekście były wypisywane nie jako kolejny numer znaku w tekście, ale jako numer wiersza i znaku w wierszu.

• naiwny (oczywisty) algorytm (1 pkt);

• algorytm Rabina-Karpa (1 pkt);

• algorytm Knutha-Morrisa-Pratta (1 pkt);

• wzorzec1.txt, tekst1.txt
• wzorzec.txt, tekst.txt

Uwagi.

• Program powinien wypisywać wszystkie pozycje, na których znaleziono wystąpienie wzorca.
• W celu ułatwienia sprawdzania rozwiązań, w zadaniu AL13.2 proszę dołączyć wydruk z wynikami: znalezione wystąpienia wzorca i czasy działania (może być nawet jako komentarz dołączony do kodu)