Confronto tra stringhe contro un gruppo di parole

Question

Confronto tra stringhe contro un gruppo di parole

#1 da (2 voti)

2

Sto creando un'app in cui l'utente inserisce 8 caratteri. Dopo aver inserito la stringa devo vedere se è una parola di otto lettere. In caso contrario, controlla se contiene una parola di sette lettere, ecc.

Sto verificando un determinato pool di 150k + parole. Mi interessa solo la partita più lunga possibile. C'è un modo migliore di questo:

WordPool.Contains (word.substring (0,8))
WordPool.Contains (word.substring (0,7)),
WordPool.Contains (word.substirng (1,7))
WordPool.Contains (word.substring (0,6)),
WordPool.Contains (word.substirng (1,6)),
WordPool.Contains (word.substirng (2,6))
ecc ...

Modifica

Ho dimenticato di aggiungere che sto verificando un dizionario inglese.

Finora sto usando questo:

for(i = 8; i >= 3; i--)
  for(j = 0; j <= 8 - i; j++)
      if(words.contains(word.substring(j, i))
         //do something

Modifica 2 Ho usato l'approccio sopra definito solo con una piccola modifica. Sto usando alcuni agenti di background che cercano tutti una parola di una certa lunghezza. Tutti quindi restituiscono un risultato e scelgo quello che dà all'utente il punteggio più alto.

algorithms strings string-matching

posta Ivan Crojach Karačić 26.11.2013 - 20:44

fonte

1 risposta

Leggi altre domande sui tag algorithms strings string-matching

Un'alternativa all'avere campi che potrebbero non essere usati in una classe Come condividere un file su più progetti

score 2 · Accepted Answer

La pre-elaborazione del tuo pool di parole in un trie renderebbe la ricerca più lunga facile. Attraversa il trie fino a che non puoi andare oltre. Dovresti comunque provarlo per ogni posizione di partenza, però. Ad esempio:

wordPool.longestMatch("deadbeef");
wordPool.longestMatch("eadbeef");
wordPool.longestMatch("adbeef");
wordPool.longestMatch("dbeef");
wordPool.longestMatch("beef");
wordPool.longestMatch("eef");
wordPool.longestMatch("ef");
wordPool.longestMatch("f");

Potresti anche cortocircuitare se hai già trovato una corrispondenza più lunga della lunghezza delle sottosequenze rimanenti. L'esempio troverebbe "morto" sulla prima riga e "manzo" sulla quinta riga, quindi potresti saltare automaticamente le ultime tre sottosequenze.