Arbol de sufijos Patricia ayuda!

Primero de todo: que estas estudiando y para que asignatura es? Situanos porque las respuestas pueden variar muchisimo, si estas estudiando Programación II o Estructuras de Datos I o por ejemplo, Linguistica Computacional, o por ejemplo Algebra II con teoria de gráfos unidireccionales... Teoria de automatas...

Situanos.

2º) http://en.wikipedia.org/wiki/Radix_tree

Creo que se explica bastante bien.

Yo tiraría por ver cómo se puede formar la subcadena. Es decir, el "man" puede ser un nodo entero o formar parte de varios (hasta 3). En el caso del ejemplo de la wikipedia, para llegar a romanus se pasa por OM-AN, pero en otro podría ser MA-NA o M-A-N, etc... Vamos, que sería ir analizando los nodos para ver si entre sus antecesores y sucesores se forma la subcadena. Puedes buscarte la letra del medio de la subcadena en los nodos y en los que la contengan tiras hacia arriba buscando la M y hacia abajo buscando la N (cuando digo hacia arriba es hacia la izquierda en el propio nodo y luego ya hacia el antecesor). Una vez tengas localizado el MAN ya es tirar hacia abajo por el camino más largo.

Así de primeras no se me ocurre mucho más...

Salu2

No tenía mucha idea de este árbol, la verdad. Ahora sé un poquito (muy poquito) más.

Según he podido entender en cada nodo se guarda una palara y el nº de BIT dónde mirar para decidir el camino de la izquierda o la derecha. Para buscar las palabras que comparten prefijo por lo visto se empieza por la raíz y se va elegiendo camino hasta que nos topamos con un nodo cuyo nº de BIT es mayor que la longitud en bits del prefijo que buscamos. Entonces paramos en ese nodo que se convierte en el raíz del árbol de palabras que comparten prefijos. (Sacado de -> http://www.codeproject.com/KB/string/PatriciaTrieTemplateClass.aspx)

Las palabras que contienen la subcadena "caca" son el conjunto de las:

a) Las que tienen el PREfijo "caca" (Estas si sabes localizarlas)

b) Las que tienen el prefijo Xcaca

c) Prefijo XYcaca

d) Prefijo XYZcaca
.
.
.
n) Las que tienen el SUfijo "caca" (Estas creo que tb se pueden encontrar fácilmente)

Podrías ir probando con estos prefijos "genéricos" con BITS "difusos", de tal forma que cuando llegues a una bifurcación tires por los dos lados al mismo tiempo (bueno, al mismo tiempo no, utilizando backtracking). La cosa sería ver hasta dónde sigues construyendo prefijos de palo (palabra más larga con el sufijo "caca"??)...

Ahora bien, de la complejidad O() npi (Intuitivamente creo que es menor que ir buscando la subcadena en cada nodo de longitud >= que el palabro buscado, pero cuánto, no lo sé)

Salu2

#6 Teniendo en cuenta que puedes crear prefijos de longitud infinita, pues tienes un algoritmo infinito, y puede ser que un palabro no sea subcadena de ninguna palabra.

Tienes 29 posibilidades de la 'a' a la 'z' en cada posicion que te inventas

zcaca
xcaca
ycaca
...

zzcaca
zxcaca
...
xzcaca
xycaca
...
aacaca
zzzcaca
....
aaacaca

pero no sabes donde ni cuando parar. O(29ⁿ) siendo n las posiciones del prefijo que te inventas.

Sigo en mis trece, no se puede.

Si se puede como dices las palabras que empiezan por caca- ( Que para eso es el arbol ) o las que terminan en -caca. ( Dependiendo de como este implementado, en mi caso el primero ( prefijos )

PD: Que significa esta linea:

A given suffix tree can be used to search for a substring, pat[1..m] in O(m) time.

Con un sufijo dado no? Pero y si no te lo dan ? xD

Vaya ahi pone que se puede hacer en un patricia en O(m + log n) pero no lo explica, explica haciendolo de otra forma.

Pero la cosa es, que en el ejemplo ese, solo tiene 1 string y la "p", pero yo tengo un diccionario (strings) y una "p" que es cualquier permutacion de una secuencia de hasta 5 caracteres de longitud m hasta 2 (abcd -> tambien valen ab ac ad abc abd etc.. ). ( salen unos 100.000) , por lo que es O(m² + log n*q) siendo "q" los 100k esos.

Gracias de todas formas.

Mierda, si que se puede
http://en.wikipedia.org/wiki/Suffix_tree#Applications

pero no dicen como.

EDIT:
Esto he encontrado, dice que se puede resolver en O(n+k) creo que n es el tamaño de la substring y k el numero de ocurrencias donde se encuentre la subcadena. A ver si encuentro alguno de los algoritmos que dice al final " the Knuth-
Morris-Pratt, Boyer-Moore, or even the Aho-Corasick algorithm"

Suffix trees yield a very attractive solution to this database problem. A
generalized suffix tree T for the strings in the database is built in 0(m) time and,
more importantly, requires only 0(m) space. Any single string S of length n is found
in the database, or declared not to be there, in 0(n) time. As usual, this is
accomplished by matching the string against a path in the tree starting from the root.
The full string S is in the database if and only if the matching path reaches a leaf of
T at the point where the last character of S is examined. Moreover, if S is a substring
of strings in the database then the algorithm can find all strings in the database
containing S as a substring. This takes O(n + k) time, where k is the number of
occurrences of the substring. As expected, this is achieved by traversing the subtree.
below the end of the matched path for S. If the full sting S cannot be matched
against a path in T, then S is not in the database and neither is it contained in any
string there. However, the matched path does specify the longest prefix of S that is
contained as a substring in the database.
The substring problem is one of the classic applications of suffix trees. The
results obtained using a suffix tree are dramatic and not achieved using the Knuth-
Morris-Pratt, Boyer-Moore, or even the Aho-Corasick algorithm.

Joer me he leido todo y siempre hablan de lo mismo, tener 1 cadena y encontrar en ella la subcadena, pero yo tengo un diccionario entero :S, le van a dar por el culo, total es 1 de 4 practicas...

Necesito un 2 sobre 10 en las practicas, malo sera....

Bueno por lo menos esto se queda aqui para la posteridad , igual a alguien le sirve.