Problem A - Zapytania
Problem B - Analizator ciągów
Problem C - Dopasowywanie wzorca do tekstu
Problem D - Problem z trójkątem

 

1980

Problem C - Dopasowywanie wzorca do tekstu


Opis

Raczej prostym zadaniem jest porównanie dwóch łańcuchów znakowych w celu sprawdzenia, czy są one takie same. Jednakże, jeśli jeden z łańcuchów (który nazwiemy "wzorcem") będzie mógł zawierać znaki "zastępcze" - znaki, które pasują do od zera do dowolnej liczby innych znaków - to problem ten stanie się bardziej wyzywający. Na przykład, załóżmy, że porównanie dotyczy 26 liter oraz znaku specjalnego *. Znak * oznacza "dowolną grupę liczącą zero lub więcej znaków". Wzorzec A*B pasuje do łańcuchów AB, AWB, AMNB, ACEFGHUKPWODJGPOIJWLAB, itp. Podobnie, wzorzec A*B*C pasuje do łańcuchów ABC, ABBABC, itp.

Napisz program, który odczyta dowolne pary wzorca i łańcucha znakowego, wypisze je i sprawdzi, czy łańcuch pasuje do wzorca.

Wszystkie znaki (litery od A-Z) muszą pasować do danego wzorca. Jeśli łańcuch pasuje do wzorca, program powinien wypisać odpowiednią wiadomość oraz podać wartość każdego "znaku zastępczego" *. Tj. mając dany wzorzec A*B*B oraz łańcuch ABDDGB, powinien wypisać, że łańcuch pasuje do wzorca, a *1 (pierwszy znak zastępczy) nie pasuje do żadnych znaków, *2 pasował do DDG. Program powinien odczytać dowolną liczbę takich par wzorca i łańcucha znakowego, wypisać je wraz z raportem na temat wyników próby dopasowania wzorca.

 

Specyfikacja wejścia

Na wejściu program otrzyma ciąg wierszy. W każdym wierszu będą zawarte dwa łańcuchy tekstowe, zbudowane z liter A-Z oraz znaku *. Łańcuchy te będą oddzielone od siebie co najmniej jedną spacją. Jeśli program napotka wiersz pusty, to powinien zakończyć działanie. Pierwszy łańcuch jest wzorcem. Drugi łańcuch jest sprawdzanym tekstem.
 

Specyfikacja wyjścia

Dla każdej pary wzorzec - łańcuch należy wypisać tę parę, następnie wiadomość, czy tekst pasuje do wzorca, a dalej należy podać do jakich fragmentów łańcucha pasowały kolejne znaki zastępcze (możemy je numerować *1, *2...). Jeśli znakom zastępczym można przydzielić znaki łańcucha na kilka sposobów, to wybierz taki, który pierwszemu znakowi zastępczemu przydziela najmniej znaków z tekstu. Jeśli to nie rozwiązuje problemu, z pozostałych sposobów wybierz taki, który przypisuje najmniej znaków do drugiego znaku zastępczego, itd. Do wzorca musi pasować cały tekst ze wszystkimi znakami od A do Z.

 

Przykładowe dane wejściowe

A*B*B ABDDGB
 

Przykładowe dane wyjściowe

A*B*B ABDDGB
STRING MATCHES THE PATTERN
*1 NO CHARACTERS
*2 DDG

 



List do administratora Serwisu Edukacyjnego Nauczycieli I LO

Twój email: (jeśli chcesz otrzymać odpowiedź)
Temat:
Uwaga: ← tutaj wpisz wyraz  ilo , inaczej list zostanie zignorowany

Poniżej wpisz swoje uwagi lub pytania dotyczące tego rozdziału (max. 2048 znaków).

Liczba znaków do wykorzystania: 2048

 

W związku z dużą liczbą listów do naszego serwisu edukacyjnego nie będziemy udzielać odpowiedzi na prośby rozwiązywania zadań, pisania programów zaliczeniowych, przesyłania materiałów czy też tłumaczenia zagadnień szeroko opisywanych w podręcznikach.



   I Liceum Ogólnokształcące   
im. Kazimierza Brodzińskiego
w Tarnowie

©2017 mgr Jerzy Wałaszek

Dokument ten rozpowszechniany jest zgodnie z zasadami licencji
GNU Free Documentation License.