cautari rapide intr-un dictionar

[•cipy]

Salut,

Am pus urmatoarea problema (pe la inceput de ianuarie) unuia din greucenii* de aici (nu dam nume ) si nici pana in ziua de azi n-am primit nici macar un raspuns, gen: a) n-am timp, b) n-am idee (dubios*), c) nu rezolv problemele utilizatorilor (si mai dubios)

Asa ca va invit la o dezbatere: (am gasit ceva idei/alg pe wikipedia, dar nu strica idei in plus )

----

se da un dictionar (de cuvinte) si se cere (ideea pt) cea mai buna implementare (in pseudo cod cu numele algoritmilor, eventual al structurilor de date folosite) a unei functii care pentru o regula/pattern de forma AB???CDE??Z ori ???ABC??AD?AAA, etc (unde ? poate fi orice caracter (dar trebuie sa fie unul), ? poate apare oriunde in regula):

1. intoarce numarul de cuvinte din dictionar care respecta regula data (eventual doar false, true)
2. intoarce toate cuvintele din dictionar care respecta regula data


pt 1. se accepta si valori aproximative cu numarul de cuvinte care ar putea/trebui sa respecte regula

instructiuni:

+ dictionarul poate fi analizat inainte (aici complexiteatea codului/structurilor nu conteaza)
+ functiile de cautare trebuie sa fie (f.) rapide
+ o librarie regexp generica nu se califica la "cea mai buna implementare"


Merci,

[•Cosmin]

Care e sursa problemei?

[•cipy]

(problema practica legata de un hobby; am formulat-o gen problema de concurs/info)

[•flmanea]

Problema mi se pare ca e similara cu dictionary matching. Despre dictionary matching cu "don't cares" (?) gasesti o lucrare foarte buna la adresa: http://www.cs.nyu.edu/cs/faculty/cole/papers/CGL04.ps , si mai poti afla mai multe din lucrarile citate de autori la bibliografie.

[•cipy]

merci