Поиск всех возможных общих подстрок из файла, состоящего из строк, используя c ++

Question

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

E.g входной файл отсортирован:

AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAC    
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAG
AAAAAAAATTAGGCTGGG
AAAAAAAATTGAAACATCTATAGGTC
AAAAAAACTCTACCTCTCT
AAAAAAACTCTACCTCTCTATACTAATCTCCCTACA

и мой желаемый результат:

AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAC    
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAG
AAAAAAAATTAGGCTGGG
AAAAAAAATTGAAACATCTATAGGTC
AAAAAAACTCTACCTCTCTATACTAATCTCCCTACA

[EDIT] Каждая строка, которая является подстрокой любой другой строки, должна быть удалена.

Answer 1

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

ААА БББ ААББ ААА

Здесь у нас есть только две возможные входные буквы, поэтому нам просто нужна гистограмма размера 2.

• aaa - Hist [0] = 3, исторических [1] = 0: Новый - добавить к ответу
• bbb - исторических [0] = 0, исторических [1] = 3: новый - добавить к ответу
• aabb - исторических [0] = 2, исторических [1] = 2: новый - добавить к ответу
• ab - исторических [0] = 1, исторических [1] = 1: новый - добавить к ответу

• ааа - гист [0] = 3, гист [1] = 0: уже существует! Не добавляйте к ответу.

  Узким местом вашей реализации будут сравнения гистограмм , и для этого существует множество возможных реализаций.

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

  Более быстрый, но гораздо более сложный для реализации, использует хеш-таблицу для хранения вашего ответа и использует гистограмму для генерации хеш-кода. Было бы затруднительно объяснить этот подход здесь.

Answer 2

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

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

vector<string> unique_lines;
for (unsigned int j=0; j < lines.size() - 2; ++j)
{
    const string& line = lines[j];
    const string& next_line = lines[j + 1];

    // If the line is not a substring of the next line,
    // add it to the list of unique lines.
    if (line.size() >= next_line.size() || 
        line != next_line.substr(0, line .size()))
        unique_lines.push_back(line);
}

// The last line is guaranteed to not be a substring of any
// previous line as the lines are sorted.
unique_lines.push_back(lines.back());

// The desired output will be contained in 'unique_lines'.

Answer 3

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