Je suggère d'utiliser un dictionnaire. Utilisez des chaînes comme clés et une liste de chaînes comme valeur. Marquez les chaînes qui seront recherchées et ajoutez la chaîne entière à votre dictionnaire une fois pour chaque jeton. (Youn peut utiliser la méthode split pour marquer vos chaînes.Utilisez l'espace comme délimiteur.) Par la suite, chaque fois que vous avez besoin de rechercher, vous marquez la chaîne de recherche et effectuez une recherche pour chaque token dans votre dictionnaire.
Ainsi, si vous avez ajouté les chaînes suivantes: foo, baz, bar, blah, bar foo, foo baz
Votre dictionnaire contient des entrées:
foo: foo, foo bar, foo baz baz : baz, foo bar baz : bar, foo bar bla: bla
Si vous recherchez alors pour "foo bar",
votre sortie est l'union des entrées stockées sous foo et bar comme donc: "foo bar": = foo, bar
foo: foo, foo bar, foo baz union bar: bar, foo bar
donnant: foo, foo bar, foo baz, bar
EDIT: Je viens de remarquer que vous voulez seulement des correspondances complètes ou partielles, c'est-à-dire que foo baz n'est pas acceptable.La solution facile consiste à post-traiter les résultats - limiter la longueur de la chaîne de recherche et de la chaîne cible à la longueur de la chaîne la plus courte, puis comparer la chaîne tronquée avec la chaîne non modifiée. Acceptez seulement ceux qui sont équivalents.
EDIT: Donc, il s'avère que foo baz est en effet un match. Ne tenez pas compte du paragraphe ci-dessus (première édition). Voir (C#) Code comme suit:
class DictionarySearch
{
private Dictionary<string, List<string>> dict;
public DictionarySearch()
{
dict = new Dictionary<string, List<string>>();
}
/// <summary>
/// Add a string e.g. foo bar to the dictionary
/// </summary>
/// <param name="s">string to be added</param>
public void addString(string s)
{
//tokenize string
string[] words = s.Split(new char[] { ' ' });
//add each token to the dictionary as a key with the matching value being s
foreach (string w in words)
{
if (dict.ContainsKey(w))
{
dict[w].Add(s);
}
else
{
dict.Add(w, new List<string>());
dict[w].Add(s);
}
}
}
/// <summary>
/// Find all strings which match at least one token
/// </summary>
/// <param name="s">string of tokens (words) to be matched</param>
/// <returns>List of strings matching at least one word</returns>
public IList<string> getMatches(string s)
{
//split search string into words
string[] words = s.Split(new char[] { ' ' });
List<string> output = new List<string>();
//retrieve from dictionary list of strings matching each word.
foreach (string w in words)
{
if (dict.ContainsKey(w))
{
output.AddRange(dict[w]);
}
else
{
continue;
}
}
return output;
}
}
Étant donné un dictionnaire avec des chaînes m avec des mots q par chaîne et n mots uniques, et une chaîne de recherche avec des mots l la complexité du temps sont les suivants:
Remplir la structure de données: O (q m T [dictionnaire-insert]). Une insertion doit être effectuée pour chaque mot
Trouvez une chaîne: O (l * T [dictionnaire-trouver]). Une recherche de dictionnaire par mot dans la chaîne de recherche.
Le coût réel dépend de l'implémentation de votre dictionnaire. Un dictionnaire basé sur une table de hachage entraîne un coût O (1) à la fois pour l'insertion et la recherche. Un dictionnaire basé sur un arbre binaire entraîne un coût O (lg n) à la fois pour l'insertion et la recherche.
sont les chaînes de mots anglais ou peuvent-ils contenir des caractères? Sont-ils sensibles à la casse? – Adamski
@Adamski Ce sont des mots anglais et ne sont pas sensibles à la casse; Cependant, ce sont des mots très techniques, comme des choses que vous ne trouveriez pas dans un dictionnaire. –
Si le dictionnaire contenait "foob" cela serait-il retourné si je cherchais "foo" ou êtes-vous uniquement concerné par des correspondances exactes? – Adamski