Какие алгоритмы используются для поиска подслов в словах?

То, как вы это сделаете, будет зависеть от того, как устроен ваш словарь. Если это отсортированный список слов, вы можете использовать двоичный поиск, чтобы найти первое слово, начинающееся с «папа», а затем просмотреть только те, которые используют StartsWith и Substring. То есть:

List<string> Words = LoadWords(); // however you load them
Words.Sort();

// Now, search for "dad" (or whatever)
string prefix = "dad";

int index = Words.BinarySearch(prefix);

// If the returned index is negative, the word wasn't found.
// The index is the one's compliment of the the place where it would be in the list.
if (index < 0)
{
    index = ~index;
}

for (int i = index; i < Count && Words[i].StartsWith(prefix))
{
    Console.WriteLine(Words[i].Substring(prefix.Length));
}

Это должно быть очень быстро. Сортировка является единовременной стоимостью после загрузки. А можно и вовсе исключить, если хранить словарь в отсортированном порядке. Бинарный поиск — O(log n), где n — количество слов в словаре.

Если ваш словарь неупорядочен, то вам придется просмотреть все слова, что займет много времени.

Есть и другие организации для вашего словаря, которые заставят его занимать намного меньше места и потенциально могут быть быстрее. Это несколько сложнее и требует гораздо больше времени для создания, чем создание отсортированного списка.

Это звучит как идеальное использование для Trie/DAWG (направленный ациклический граф слов). Я понимаю, что дерево Патрисии - это разновидность дерева. Здесь есть хорошая статья о попытках и их реализации.

Циклы for могут быть довольно быстрыми для очень маленьких словарей. Но если у вас есть совпадающие наборы из тысяч слов, это будет очень медленно. Предполагая, что ваш словарь отсортирован (если не отсортирован), вы можете использовать функцию BinarySearch, чтобы найти первый и последний элементы диапазона, а затем использовать цикл for для создания результатов.

Чтобы быть более практичным, у меня есть (отсортированный) словарь с 354984 словами, включая эти 35 слов, начинающихся с папы: папа, папа, дада, дадаизм, дадаизмы, дадаист, дадаист, дадаистически, дадаисты, дадап, дадас, папа сгорел, папа, папы , папа, даддл, даддл, даддл, даддлинг, папа, папа, папа, папа, папа, папочка, папа, даденхудд, дадинг, дадо, дадоед, дадо, дадоин, дадо, дадушо, папы и дадучус. Если я буду следовать подходу Джима, мне придется выполнить 35 "StartsWith", что нормально. В случае префикса "sat" у меня 228 слов, а в случае префикса "cat" у меня 692 слова. Для размера моего словаря мне нужно в общей сложности 40 сравнений строк (в худшем случае), чтобы найти первый и последний элементы.

Если вы хотите использовать любую реализацию trie, убедитесь, что она поддерживает как минимум числа и тире, если ваш словарь включает такие записи, как 1st или в реальном времени.

Самый известный, который я знаю, это "knuth morris pratt string алгоритм сопоставления".

Если вы посмотрите на ссылку, есть некоторые другие, такие как алгоритм поиска строки Бойера-Мура, ... Это общие алгоритмы, но если вас интересуют особые случаи, такие как начало, ... в большинстве случаев языки имеют это случаях, например, в C# вы можете использовать StartsWith, EndsWith, нет необходимости реализовать их снова.

если вам нужно что-то простое, вы можете попробовать это:

        string[] dict = new string[] { "dada", "dadaism", "daddled", "daddling" };
        string prefix = "dad";

        var words = from d in dict
                    where d.StartsWith(prefix)
                    select d.Substring(prefix.Length);

Вы можете использовать TRIE для этого. Полную реализацию и руководство можно найти здесь.

По сути, в этой структуре вы в конечном итоге перейдете от корня к «d», затем к «a», затем к «d». Вы дойдете до того, что вам нужны все слова, начинающиеся с «папа». Учитывая, что теперь это корневой узел, все, что вам нужно сделать, это изучить все возможные пути под ним, и вот ваш алгоритм