Recentemente ho avuto una questione intervista che è andato qualcosa di simile:Che cos'è un algoritmo tipico per trovare una stringa all'interno di una stringa?
Data una stringa di grandi dimensioni (pagliaio), trovare una stringa (ago)?
Ero un po 'perplesso per trovare una soluzione decente.
Qual è il modo migliore per avvicinarsi a questo che non ha una complessità di tempo scadente?
È possibile utilizzare the Knuth-Morris-Pratt algorithm, che è O (n + m) dove n è la lunghezza della stringa "pagliaio" e m è la lunghezza della stringa di ricerca.
Non credo che ci sia qualcosa di meglio che guardare il pagliaio un personaggio alla volta e cercare di abbinarli all'ago.
Questo avrà una complessità temporale lineare (rispetto alla lunghezza del pagliaio). Potrebbe degradarsi se l'ago è vicino alla stessa lunghezza del pagliaio e condivide un lungo prefisso comune e ripetuto.
L'algoritmo di Knuth-Morris-Pratt @James che McNellis menziona è un miglioramento di ciò che consente di saltare alcuni caratteri dopo una corrispondenza non riuscita. Ancora O (n), però. – Thilo
Ricorda che questa è una ricerca, non un confronto. Considera la ricerca di una stringa con molti caratteri ripetuti, in una stringa con molti caratteri ripetuti, e ti renderai conto che il tuo algoritmo è in realtà O (nm) nel peggiore dei casi in cui n e m sono ciascuno la lunghezza di una stringa. Il prodotto di due variabili non è classificato come lineare (non è uguale a una costante sconosciuta per volta una variabile), e certamente non è buono come ad es. la somma di queste due variabili, che è realizzabile. – Steve314
@ Steve314: Questo è ciò che intendevo per "degradare se l'ago è vicino alla stessa lunghezza del pagliaio e condivide un lungo prefisso comune e ripetuto" (il prefisso avrebbe dovuto essere una sottostringa, però). – Thilo
Questo problema è discusso in Hacking a Google Interview Practice Questions – Person A. La loro soluzione campione:
bool hasSubstring(const char *str, const char *find) {
if (str[0] == '\0' && find[0] == '\0')
return true;
for(int i = 0; str[i] != '\0'; i++) {
bool foundNonMatch = false;
for(int j = 0; find[j] != '\0'; j++) {
if (str[i + j] != find[j]) {
foundNonMatch = true;
break;
}
}
if (!foundNonMatch)
return true;
}
return false;
}
sarebbe buono per restituire l'indice di inizio della partita. Nello scenario tradizionale del pagliaio, sai già che l'ago è lì dentro. da qualche parte. :-) – Thilo
Questo è un buon collegamento! http://courses.csail.mit.edu/iap/interview/materials.php – Courtney85
Mi piace il Boyer-Moore algorithm. È particolarmente divertente da implementare quando ci sono molti aghi da trovare in un pagliaio (per esempio, pattern di spam probabili in un corpus di e-mail).
+1; Molto bello; Non avevo familiarità con questo. Per gli aghi multipli, potresti anche considerare l'algoritmo Aho-Corasick. –
+1 Ho saputo di Boyer-Moore molti anni fa nella rivista "Computer Language" ... un gioiello (sia l'algoritmo che la rivista) –
A un algoritmo tipico sarebbe il seguente, con indici di stringa che vanno da 0 a M-1.
Restituisce la posizione della corrispondenza o -1 se non trovata.
foreach hpos in range 0 thru len(haystack)-len(needle):
found = true
foreach npos in range 0 thru len(needle):
if haystack[hpos+npos] != needle[npos]:
found = false
break
if found:
return hpos
return -1
Ha una performance ragionevole dal momento che controlla solo il maggior numero di personaggi in ogni posizione pagliaio come necessario per scoprire non c'è alcuna possibilità di un incontro.
Non è necessariamente l'algoritmo più efficiente, ma se il tuo intervistatore si aspetta che tu conosca tutti gli algoritmi ad alte prestazioni in cima alla tua testa, sono irrealistici (vale a dire, pazzi). Un buon sviluppatore conosce bene le basi e come trovare le cose avanzate se necessario (ad es., Quando c'è un problema di prestazioni, non prima).
La prestazione varia tra O (a) e O (ab) a seconda dei dati effettivi nelle stringhe, dove aeb sono rispettivamente il pagliaio e le lunghezze dell'ago.
Un possibile miglioramento consiste nel memorizzare, all'interno del ciclo npos, la prima posizione superiore a hpos, in cui il carattere corrisponde al primo carattere dell'ago.
In questo modo è possibile saltare gli hpos in avanti nella prossima iterazione poiché si sa che non ci può essere una corrispondenza possibile prima di quel punto. Ma ancora, potrebbe non essere necessario, a seconda dei requisiti di prestazione. Dovresti calcolare da solo l'equilibrio tra la velocità e la manutenibilità.
Uno di quei casi in cui l'abilità di 'continuare' un ciclo esterno da un interno il ciclo sarebbe fantastico. –
@Mike: "goto considerato fantastico"? ;-) –
Penso che ci sia una pausa/contine anche con un'etichetta. Non c'è bisogno di andare agli estremi. – Thilo
Il problema generale è string searching; ci sono molti algoritmi e approcci a seconda della natura dell'applicazione.
Alcune strutture di dati indice avanzate vengono utilizzate anche in altre applicazioni. Suffix trees sono molto utilizzati in bioinformatica; qui hai un lungo testo di riferimento, e poi hai molte stringhe arbitrarie per le quali vuoi trovare tutte le occorrenze. Una volta che l'indice (cioè l'albero) è costruito, la ricerca di modelli può essere eseguita in modo abbastanza efficiente.
Per una risposta all'intervista, penso che sia meglio mostrare anche l'ampiezza. Conoscere tutti questi diversi algoritmi e quali scopi specifici servono meglio è probabilmente meglio che conoscere un solo algoritmo a memoria.
"Per una risposta all'intervista, penso che sia meglio mostrare anche l'ampiezza." Non lo so. Dovresti saperlo in cima alla tua testa? In una situazione di vita reale, dovresti cercare l'algoritmo su Internet. In un'intervista, mi aspetterei che qualcuno realizzasse un'implementazione come Brian o paxdiablo show, ed essere in grado di spiegare quando si comporterebbero male. – Thilo
Tenere a mente il mio background è nel mondo accademico; facciamo molta lettura dei documenti di indagine. Immagino che la gente si aspetterebbe che i candidati sappiano * SU * questi in cima alla loro testa, almeno al livello di dettaglio mostrato nel mio post (cioè non molto). Hai ragione, i dettagli degli algoritmi possono essere consultati in rete, ma hanno bisogno di sapere * SU * loro, in modo che sappiano cosa cercare e che esista. Inoltre, suppongo dipenda dal tipo di posizione per cui stai intervistando. A volte hanno solo bisogno di fare le cose. Altre volte hanno bisogno di persone che sappiano cosa sta realmente accadendo là fuori. – polygenelubricants
Altro esempio: viene chiesto al candidato di risolvere TSP, senza dare via il nome del problema. Un candidato arriva rapidamente con un algoritmo di forza bruta 'O (N!)', Sottolineando correttamente che è lento ecc. Un altro riconosce immediatamente il suo TSP, cosa significa in termini di NP-completezza, quali approcci sono stati tentati, esistenza di algoritmi approssimativi ma di buona approssimazione (anche senza conoscere i loro dettagli), ecc. Penso che le persone sarebbero d'accordo sul fatto che il secondo candidato sia migliore del primo, almeno per certe posizioni. – polygenelubricants
Ecco uno presentation di un qualche algoritmo (collegato senza vergogna all'Università Humboldt). contiene alcuni buoni algoritmi come Boyer More e Z-box.
Ho usato l'algoritmo Z-Box, ho trovato che funziona bene ed era più efficiente di Boyer-More, ma ha bisogno di tempo per avvolgerlo.
il modo più semplice è "pagliaio" .Contains ("ago");) solo divertimento, non prenderlo sul serio. Penso che tu abbia già la tua risposta.
Ottenuto a metà strada digitando una risposta quando l'ho visto, ho letto l'articolo e ho capito che era la stessa cosa. Non ne ho mai sentito parlare prima, ma nel '94 ho usato qualcosa di simile per una macchina a stati di match pattern binario. Oh bene. –