Program dopasowujący słowa ze słownika do wzorca

0

Witam serdecznie.

Mam na zaliczenie napisać następujący program:

  • Użytkownik ma podać wzór słowa np: A**T*A (gdzie * to dowolny znak)
  • Na podstawie tego wzoru wypisać wszystkie słowa z gotowego słownika które pasują do tego wzoru
  • Jeśli nie dopasowano żadnego wzoru wyświetlić komunikat, że nie można dopasować.

Ma to być program w języku C++. Kompletnie nie wiem jak się za niego zabrać... Do tej pory robiłem bardzo proste programy - ten mnie przerósł...

Pomoże ktoś?

2

Ja bym użył wyrażeń regularnych
podaje ci ktoś ten wzór
zamieniasz go na wyrażenie regularne "^A..T.A$" i wyciągasz jedno słowo ze słownika i sprawdzasz czy pasuje do wyrażenia, jeżeli tak wypisujesz przechodzisz i szukasz kolejnych

3

Wyrażenia regularne? No to sobie poczekasz na końcową odpowiedź!
Zrobiłem tu już komuś taki projekt w Qt. Odpowiedź pojawiała się praktycznie natychmiast podczas pisania (słownik miał chyba 200tysięcy słów).
Poszukaj troszkę, a znajdziesz linka do tego zip-a.

W sumie szybko to znalazłem: http://4programmers.net/Forum/Algorytmy/219341-fast_algor_-_szukanie_wg_wzorca?p=963411#id963411 (w programie jest ukryty mały błąd, łatwy do naprawienia :)).

0

MoorfoxD czy mógłbym prosić o przykładowy kod takiego programu z użyciem wyrażeń regularnych?? Bo nie mam pojęcia jak używać booosta. A z tym Qt to mi się wydaje zbyt zaawansowane jak na mój poziom. Z resztą w ogóle mi się wydaje to zbyt trudne zadanie w stosunku do tego co na zajęciach było..

Z góry dziękuję:)

0
MarQs87 napisał(a):

[..]czy mógłbym prosić o przykładowy kod takiego programu z użyciem wyrażeń regularnych?? Bo nie mam pojęcia jak używać booosta..[..]

Wyrażenia regularne są w standardzie języka jako <regex>.

0

Normalne C++11 ma wyrażenia regularne.
Mam tylko jedno pytanie, jakiego słowa nie zrozumiałeś w poście od @MarekR22 ?

1

Nie wiem czy można podawać źródła do innych forum jak nie to furious to wytnie <ort>za nim</ort> ktokolwiek zdąży to przeczytać :
http://cpp0x.pl/artykuly/?id=47
O Qt się nie martw ort! chodziło pewnie, żeby zrobić po prostu zwykłe sprawdzanie po literce co będzie miało dużo mniejszą złożoność czasową, ja osobiście myślę, że nie będzie, aż tak zauważalnej różnicy, ale nie jestem pewien. Po prostu moje rozwiązanie zajmie ci 10 razy mniej czasu bo jest banalne w zaimplementowaniu

2

Aście się uparli na te regexpy. Najwyraźniej ktoś się musi przekonać na własnej skórze, dlaczego to jest najgorsze z możliwych rozwiązań.

1 użytkowników online, w tym zalogowanych: 0, gości: 1