Как найти все строки братства?

Самый эффективный алгоритм, который я могу придумать:

• Настройте хеш-таблицу для исходной строки. Пусть каждая буква будет ключом, а количество раз, которое буква появляется в строке, будет значением. Назовите эту хеш-таблицу inputStringTable.
• Разберите входную строку и каждый раз, когда вы видите символ, увеличивайте значение хеш-записи на единицу.
• для каждой строки в файле
• создать новую хеш-таблицу. Назовите это BrotherStringTable.
• для каждого символа в строке добавить единицу в новую хеш-таблицу. Если BrotherStringTable[character] > inputStringTable[character], эта строка не является братом (один символ появляется слишком много раз)
• после анализа строки сравните каждое значение inputStringTable с соответствующим значением BrotherStringTable. Если один отличается, то эта строка не является братской строкой. Если все совпадают, то строка является строкой-братом.

Это будет O(nk), где n — длина входной строки (любые строки длиннее входной строки могут быть немедленно отброшены), а k — количество строк в файле. Любой алгоритм на основе сортировки будет O(nk lg n), поэтому в некоторых случаях этот алгоритм работает быстрее, чем алгоритм на основе сортировки.

Сортировка каждой строки с последующим ее сравнением дает что-то вроде O(N*(k+log S)), где N — количество строк, k — длина ключа поиска, а S — средняя длина строки.

Кажется, что подсчет вхождений каждого символа может быть здесь возможным способом (при условии, что строки имеют разумную длину). Это дает вам O(k+N*S). Будет ли это на самом деле быстрее, чем сортировка и сравнение, очевидно, будет зависеть от значений k, N и S.

Я думаю, что на практике эффект перезаписи всех строк в случае сортировки приведет к снижению производительности по сравнению с любым алгоритмом, который не изменяет строки...

повторять, сортировать, сравнивать. это не должно быть слишком сложно, верно?

Предположим, ваш алфавит от «а» до «я», и вы можете индексировать массив на основе символов. Затем для каждого элемента в массиве из 26 элементов вы сохраняете количество раз, которое эта буква появляется во входной строке.

Затем вы просматриваете набор строк, которые вы ищете, и перебираете символы в каждой строке. Вы можете уменьшить счетчик, связанный с каждой буквой в (копии) массива счетчиков из ключевой строки.

Если вы завершаете свой цикл по строке-кандидату без остановки и видите то же количество символов, что и во входной строке, это совпадение.

Это позволяет пропустить сортировку в пользу копирования массива с постоянным временем и одной итерации по каждой строке.

EDIT: После дальнейшего размышления это эффективно сортирует символы первой строки с использованием групповая сортировка.

Я думаю, что вам поможет тест, являются ли две строки анаграммами. Вот как вы можете это сделать. Я предполагаю, что на данный момент строка может содержать 256 символов ascii.

#define NUM_ALPHABETS 256
int alphabets[NUM_ALPHABETS];

bool isAnagram(char *src, char *dest) {
    len1 = strlen(src);
    len2 = strlen(dest);
    if (len1 != len2)
        return false;

    memset(alphabets, 0, sizeof(alphabets));
    for (i = 0; i < len1; i++)
        alphabets[src[i]]++;
    for (i = 0; i < len2; i++) {
        alphabets[dest[i]]--;
        if (alphabets[dest[i]] < 0)
            return false;
    }

   return true;
}

Это будет работать за O (mn), если у вас есть строки «m» в файле средней длины «n».

• Отсортируйте строку запроса
• Iterate through the Collection, doing the following:
  • Sort current string
  • Сравните со строкой запроса
  • Если он совпадает, это матч "братства", сохраните его/индекс/что хотите

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

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

Шаги будут такими:

• построить гистограмму тестовой строки (обнулить массив int histogram[128] и увеличить позицию для каждого символа в тестовой строке)

• для каждой входной строки

  • для каждого символа во входной строке c проверьте, равен ли histogram[c] нулю. Если да, то это не совпадение и восстановить гистограмму.

    • decrement histogram[c]

  • чтобы восстановить гистограмму, переместите входную строку обратно к ее началу, увеличивая, а не уменьшая

В лучшем случае требуется два увеличения/уменьшения массива для каждого символа на входе.

Наиболее эффективный ответ будет зависеть от содержимого файла. Любой алгоритм, который мы придумаем, будет иметь сложность, пропорциональную N (количество слов в файле), L (средняя длина строк) и, возможно, V (разнообразие длин строк).

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

target = sort_characters("target string")
count = 0
foreach (word in inputfile){
   if target.len == word.len && target == sort_characters(word){
      count++
    }
 }

Я бы рекомендовал:
для каждой строки в текстовом файле:

1. сравнить размер с «исходной строкой» (размер строк братства должен быть одинаковым)
2. сравните хэши (CRC или хэш фреймворка по умолчанию должны быть хорошими)
3. в случае справедливости сделайте более точное сравнение с отсортированными строками.

Это не самый быстрый алгоритм, но он будет работать для любого алфавита/кодировки.

Вот еще один метод, который работает, если у вас относительно небольшой набор возможных «букв» в строках или хорошая поддержка больших целых чисел. В основном состоит из написания независимой от позиции хеш-функции...

Назначьте разные простые числа для каждой буквы:

prime['a']=2;
prime['b']=3;
prime['c']=5;

Напишите функцию, которая проходит через строку, многократно умножая простое число, связанное с каждой буквой, в текущее произведение.

long long key(char *string)
{
  long long product=1;
  while (*string++) {
    product *= prime[*string];
  }
  return product;
}

Эта функция возвращает гарантированно уникальное целое число для любого набора букв, независимо от порядка их появления в строке. Получив значение для «ключа», вы можете пройтись по списку совпадающих строк и выполнить ту же операцию.

Временная сложность этого O(N), конечно. Вы даже можете повторно сгенерировать (отсортированную) строку поиска, разложив ключ. Недостатком, конечно, является то, что клавиши довольно быстро становятся большими, если у вас большой алфавит.

Вот реализация. Он создает словарь букв мастера, а строковая версия того же, что и сравнения строк, будет выполняться со скоростью C++. При создании словаря букв в пробной строке он сверяется с основным словарем, чтобы сбой в первый возможный момент - если он находит букву, не соответствующую оригиналу, или больше этой буквы, чем оригинал, он не работает . Вы можете заменить строки хэшами на основе целых чисел (согласно одному ответу относительно базы 26), если это окажется быстрее. В настоящее время хеш для сравнения выглядит как a3c2b1 для abacca.

Это должно сработать O(N log( min(M,K)) ) для N строк длины M и ссылочной строки длины K и требует минимального количества поисков пробной строки.

master = "abc"
wordset = "def cba accb aepojpaohge abd bac ajghe aegage abc".split()

def dictmaster(str):
    charmap = {}
    for char in str:
        if char not in charmap:
            charmap[char]=1
        else:
            charmap[char] += 1
    return charmap

def dicttrial(str,mastermap):
    trialmap = {}
    for char in str:
        if char in mastermap:
            # check if this means there are more incidences
            # than in the master
            if char not in trialmap:
                trialmap[char]=1
            else:
                trialmap[char] += 1
        else:
            return False
    return trialmap

def dicttostring(hash):
    if hash==False:
        return False
    str = ""
    for char in hash:
        str += char + `hash[char]`
    return str

def testtrial(str,master,mastermap,masterhashstring):
    if len(master) != len(str):
        return False
    trialhashstring=dicttostring(dicttrial(str,mastermap))
    if (trialhashstring==False) or (trialhashstring != masterhashstring):
        return False
    else:
        return True

mastermap = dictmaster(master)
masterhashstring = dicttostring(mastermap)
for word in wordset:
    if testtrial(word,master,mastermap,masterhashstring):
        print word+"\n"