Sostituisce le stringhe in base alla corrispondenza della sottostringa

L'algoritmo più efficiente sarebbe quello di costruire prima una macchina a stati finiti che a) riconosce una delle tue chiavi, e b) ha uno stato finale diverso per ogni chiave, i. e. producendo l'indice della chiave che è stata riconosciuta.

Parte a) è facile come chiamare correttamente regcomp() . Sfortunatamente, questo non produrrà l'indice di cui hai bisogno subito (parte b)), ti fornirà solo la posizione iniziale e finale della stringa riconosciuta.

Quindi, a meno che non vogliate affrontare il problema di reimplementare una routine di compilazione regolare, immagino che la vostra migliore scommessa sia quella di cercare successivamente la chiave da una tabella hash. Tuttavia, ancora una volta è difficile utilizzare un'implementazione standard della tabella hash senza attivare l'allocazione della memoria passando la chiave come stringa. Certo, puoi provare a usare un hash perfetto per la ricerca. Ciononostante, qualsiasi compromesso che ti porti via da una macchina a stati finiti con le due proprietà a) eb) subirà un strong rallentamento.

1. Crea una lista vuota per archiviare i risultati
2. Crea una coppia di valori / valori come HasmMap o Dizionario con le coppie chiave / valore turn => -foo, tween => bar, rag => baz .
3. Crea un elenco delle stringhe di input returns,between,paragraphs , ecc.
4. Iterare la mappa di chiave / valori
5. All'interno di quel ciclo itera l'elenco delle stringhe di input
6. Per ogni stringa di input che contiene la chiave come sottostringa, restituire il valore per tale chiave aggiungerlo all'elenco dei risultati creato nel passaggio 1 e uscire dal ciclo interno per continuare con la successiva iterazione esterna
7. Opzionalmente itera l'elenco dei risultati per concatenare un elenco separato da virgole come foo, bar, baz

Per prima cosa vorrei utilizzare l'algoritmo Aho-Corasick che ha O (n + m ) complessità nel tempo e O (m) nello spazio (n: lunghezza dell'input; m: lunghezza combinata dei pattern) e misura se è "abbastanza buono" (la tua chiamata) - specialmente perché sai già che puoi aspettarti esattamente una occorrenza di uno dei pattern in ogni dato input.

'HTH,