Strona 1 z 1

[c] porownywanie ciągów znaków

: 17 lis 2015, o 10:25
autor: Sniegu
Witam.
Za zadanie mam porównać wzorzec z łańcuchem. W wzorcu znak '?' znaczy dowolny znak a '*' dowolny ciąg znaków i zwrócić true lub false. Np:
ab??ca = abzzca
ta*ab=tazzzzzab

Problem pojawia się gdy jest do porównania:
ab*ab = abaaab.
Program po prostu bierze od razu kolejne 'a' i porownuje zamiast przeskoczyc do 'ab'.
Ukryta treść:    
Problem jest w tej części kodu. Dokładnie rozumiem błąd jednak nie mam bladego pojęcia jak go naprawić.

Kod: Zaznacz cały

case '*': //jak x dowolnych, to szukamy pierwszego znaku takiego jak następny po *
while ((Pos_chain < strlen(chain)) && (chain[Pos_chain] != module[Pos_mod + 1]))
Pos_chain++;
break;
Pozdrawiam.

[c] porownywanie ciągów znaków

: 17 lis 2015, o 12:10
autor: jarzabek89
Problem dość ciekawy, rozwiązanie kłopotliwe.
Po pierwsze:
Dodawajmy do dowolnego ciągu literki tak długo, aż następna literka nie będzie odpowiadała literce z łańcucha. Chyba dość oczywiste. Cofnijmy się oczywiście później o jedną literkę.
To rozwiąże problem Twego typu, ale nie rozwiąże kolejnego problemu:
Porównajmy:
ab*ab = abaaabxab
Ten algorytm jako dowolny ciąg znaków potraktuje tylko aa, a powinien aabx.
Z tego nasuwają się różne pomysły. Może analizować tekst z dwóch stron?

[c] porownywanie ciągów znaków

: 17 lis 2015, o 18:47
autor: norwimaj
Nie wiem, jaka złożoność Cię satysfakcjonuje, ale może Ci się to przyda:

Kod: Zaznacz cały

https://pl.wikipedia.org/wiki/Determinizacja_automatu_sko%C5%84czonego
. Może Twój przypadek jest trochę lepszy, niż dla dowolnego automatu.-- 17 lis 2015, o 19:01 --Dokładnie chodzi o to, że zamiast Pos_chain – pojednynczej pozycji w stringu, powinieneś przechowywać listę możliwych pozycji.

[c] porownywanie ciągów znaków

: 24 lis 2015, o 16:23
autor: Afish
Bardzo prosta i dość elegancka implementacja wyrażeń regularnych jest tutaj:
U Ciebie trzeba zamienić kropkę na pytajnik.