Trovare una stringa * e * le sottostringhe in un pagliaio

Supponi di avere una stringa (ad esempio needle). Le sue 19 sottostringhe continue sono:Trovare una stringa * e * le sottostringhe in un pagliaio

needle 
needl eedle 
need eedl edle 
nee eed edl dle 
ne ee ed dl le 
n e d l

Se dovessi costruire una regex per abbinare, in un pagliaio, una qualsiasi delle stringhe si potrebbe semplicemente fare:

/(needle|needl|eedle|need|eedl|edle|nee|eed|edl|dle|ne|ee|ed|dl|le|n|e|d|l)/

ma non sembra davvero elegante. Esiste un modo migliore per creare un'espressione regolare che abbinerà avidamente qualsiasi sottostringa di una determinata stringa?

Inoltre, se ponessi un altro vincolo, volevo abbinare solo sottostringhe più lunghe di una soglia, ad es. per sottostringhe di almeno 3 caratteri:

/(needle|needl|eedle|need|eedl|edle|nee|eed|edl|dle)/

nota: ho deliberatamente non menzionato alcun dialetto regex particolare. Si prega di indicare quale si sta utilizzando nella risposta.

fonte

2012-01-21 CAFxX

Questo sembra molto simile al problema della sottostringa comune più lunga (http://en.wikipedia.org/wiki/Longest_common_substring_problem). Ha bisogno di essere regexp? – dasblinkenlight

La lunghezza dell'ago sarà sicuramente di ordine di grandezza inferiore a quella del pagliaio. Inoltre, sono interessato a sapere quante occorrenze di una qualsiasi delle sottostringhe dell'ago appaiono nel pagliaio, non quale sia la LCS. – CAFxX

non penso che la domanda molto più semplice (http://stackoverflow.com/questions/9114402/regexp-finding-longest-common-prefix-of-two-strings) abbia una soluzione facile usando una regexp quindi probabilmente dovresti essere più specifico su ciò di cui hai veramente bisogno. Possiamo generare regexp in modo programmatico? Deos ha bisogno di essere regexp? – gorn

C'è un modo migliore per creare un'espressione regolare che corrisponda a una delle sottostringhe di una determinata stringa?

No. Ma è possibile generare facilmente tale espressione.

fonte

2012-01-21 17:23:21 Qtax

Il tuo regex 'n (?: E (?: E (?: D (?: L (?: E?)?)?)?)?)?' Corrisponde alla sottostringa 'e'? Non sembra che lo sarà. – CAFxX

Non lo farà, questo era solo un esempio di parte dell'espressione completa che conterrebbe molti di questi. – Qtax

Allora è ancora meno elegante della mia soluzione, vero? – CAFxX

Come Qtax suggerito, l'espressione

n(e(e(d(l(e)?)?)?)?)?|e(e(d(l(e)?)?)?)?|e(d(l(e)?)?)?|d(l(e)?)?|l(e)?|e

sarebbe la strada da percorrere se si voleva scrivere un'espressione regolare esplicita (egrep sintassi, eventualmente sostituire (...) da (?:...)). Il motivo per cui questo è migliore della soluzione iniziale è che la versione condensata richiede solo spazio O (n^2) rispetto allo spazio O (n^3) nella versione originale, dove n è la lunghezza dell'input. Prova questo con extraordinarily come input per vedere la differenza. Suppongo che la versione condensata sia anche più veloce con molti motori regexp in circolazione.

L'espressione

nee(d(l(e)?)?)?|eed(l(e)?)?|edl(e)?|dle

cercherà stringhe di lunghezza 3 o più a lungo.

Come sottolineato da vhallac, le espressioni regolari generate sono un po 'ridondanti e possono essere ottimizzate. Oltre allo strumento Emacs proposto, c'è un pacchetto Perl Regexp::Optimizer che speravo sarebbe stato d'aiuto in questo caso, ma un rapido controllo non è riuscito per la prima espressione regolare.

Si noti che molti motori regexp eseguono la ricerca non sovrapposta per impostazione predefinita. Controlla questo con i requisiti del tuo problema.

fonte

2012-01-30 21:57:37 krlmlr

È raggruppato in una libreria in modo che può essere utilizzato dall'esterno di Emacs? – krlmlr

Oops. Ho dimenticato di rimuovere alcuni '?:' S sul secondo: '(dle | e (dle? | Ed (le?)?) | Nee (d (le?)?)? – vhallac

-2

Forse stai solo cercando .*(.{1,6}).*

fonte

2012-02-01 18:04:59 mtanti

PS Non vedo perché non hai incluso i duplicati stringhe. Questo li includerà quindi dovrai prenderti cura di loro in modo programmatico, ad esempio utilizzando un set di hash. – mtanti

questo corrisponderà a * qualsiasi cosa * ... Non vedo come la tua risposta è correlata alla mia domanda ... – CAFxX

Corrisponde a tutte le stringhe secondarie in una stringa. O non ti sto capendo correttamente? – mtanti

ho trovato elegante almostsolution, a seconda quanto male è necessario solo un regexp.Per esempio qui è l'espressione regolare, che trova sottostringa comune (Perl) di lunghezza 7:

"$needle\0$heystack" =~ /(.{7}).*?\0.*\1/s

stringa Matching è in \ 1. Le stringhe non devono contenere caratteri null che vengono usati come separatori.

È consigliabile eseguire un ciclo che inizi con la lunghezza dell'ago e scenda fino alla soglia e cerca di far corrispondere l'espressione regolare.

fonte

2012-02-02 17:47:10 gorn

Elegante! Che ne dici del tempo di esecuzione? – krlmlr

Elegante davvero! – CAFxX

Molto impressionante. Una domanda, però: non corrisponderebbe, ad esempio, "ee ed" (o in generale brevi stringhe consecutive nel tuo pagliaio)? – vhallac

Trovare una stringa * e * le sottostringhe in un pagliaio

risposta

Problemi correlati