Нужна помощь в оптимизации программы, которая находит все возможные подстроки

Question

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

Введите:

3 // This is the user's desired number of strings
abc // So the user inputs 3 strings
abd
def
2 // This is the user's desired number of queries
7 // So the user inputs 2 queries
2

Выход:

// From the alphabetically sorted group of unique substrings,
bd // This is the 7th substring 
ab // And this is the 2nd substring

Вот моя реализация:

#include <map>
#include <iostream>
using namespace std;

int main() {
    int number_of_strings;
    int number_of_queries;
    int counter;
    string current_string;
    string current_substr;
    map<string, string> substrings;
    map<int, string> numbered_substrings;
    int i;
    int j;
    int k;

    // input step
    cin >> number_of_strings;
    string strings[number_of_strings];
    for (i = 0; i < number_of_strings; ++i)
            cin >> strings[i];
    cin >> number_of_queries;
    int queries[number_of_queries];
    for (i = 0; i < number_of_queries; ++i)
            cin >> queries[i];

    // for each string in 'strings', I want to insert every possible
    // substring from that string into my 'substrings' map.
    for (i = 0; i < number_of_strings; ++i) {
            current_string = strings[i];
            for (j = 1; j <= current_string.length(); ++j) {
                    for (k = 0; k <= current_string.length()-j; ++k) {
                            current_substr = current_string.substr(k, j);
                            substrings[current_substr] = current_substr;
                    }
            }
    }

    // my 'substrings' container is now sorted alphabetically and does
    // not contain duplicate elements, because the container is a map.
    // but I want to make the map queryable by number, so I'm iterating
    // through 'substrings' and assigning each value to an int key.
    counter = 1;
    for (map<string,string>::iterator it = substrings.begin();
                    it != substrings.end(); ++it) {
            numbered_substrings[counter] = it->second;
            ++counter;
    }

    // output step
    for (i = 0; i < number_of_queries; ++i) {
            if (queries[i] > 0 && queries[i] <= numbered_substrings.size()) {
                    cout << numbered_substrings[queries[i]] << endl;
            } else {
                    cout << "INVALID" << endl;
            }
    }

    return 0;
}

Мне нужно оптимизировать мой алгоритм, но я не уверен, как это сделать. Возможно, дело в том, что у меня есть второй цикл for для назначения новых ключей int каждой подстроке. Помощь

Answer 1

Проверьте суффикс дерева.Обычно он запускается за O (n) раз:

Эта статья была полезна для меня: http://allisons.org/ll/AlgDS/Tree/Suffix/

Answer 2

Незначительные примечания:

1. include <string>
2. careful with those } else {; one day you'll have a lot of else if branches 
and a lot of lines and you'll wonder where an if starts and where it ends
3. careful with unsigned versus signed mismatching... again, one day it will 
come back and bite (also, it's nice to compile without errors or warnings)
4. don't try to define static arrays with a variable size
5. nice with ++ i. not many know it has a slight performance boost 
(maybe not noticeable with today's processors but still)

Хотя я согласен с тем, что при необходимости используются надлежащие алгоритмы (например, сортировка по пузырькам, сортировка по куче и т. Д. Для сортировки, бинарный поиск, бинарные деревья и т. Д. Для поиска), иногда яприятно провести оптимизацию текущего кода.Представьте себе, что у вас большой проект, и для его реализации требуется что-то переписать ... не многие готовы ждать вас (не говоря уже о необходимом модульном тестировании, полном тестировании и, возможно, тестировании на соответствие).По крайней мере, мое мнение.[и да, я знаю, что некоторые скажут, что если это так сложно, то это было написано плохо с самого начала - но, эй, вы не можете спорить с программистами, которые ушли до того, как присоединились к команде: P]

Но я согласен, использование существующего материала - хорошая альтернатива, когда это необходимо.Но вернемся к делу.Я проверил это с

• 3, abc, def, ghi
• 4, 1, 3, 7, 12

Я не могу сказать,у тебя медленнее, чем у меня или наоборот;возможно, генератор случайных строк, который добавляет, может быть, 500 входов (затем вычисляет все сабвуферы), может быть лучшим тестом, но я слишком ленив в 2 часа утра.В лучшем случае мой способ написания может помочь вам (по крайней мере, мне кажется, что он проще и использует меньше циклов и назначений).Не фанат векторов, из-за небольших накладных расходов, но я использовал его, чтобы не отставать от ваших требований динамических запросов ... статический массив const был бы быстрее, очевидно.

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

В любом случае, посмотрите и скажите, что вы думаете:

#include <map>
#include <iostream>
#include <string>           // you forgot to add this... trust me, it's important :)
#include <vector>           // not a fan, but it's not that bad IF you want dynamic buffers
#include <strstream>

using namespace std;

int main ()
{
    unsigned int number_of_strings = 0;
    // string strings[number_of_strings];   // don't do this... you can't assign static arrays of a variable size
                                            // this just defaults to 0; you're telling the compiler 

    cin >> number_of_strings;

    map <string, string> substrings;
    string current_string, current_substr;
    unsigned int i, j, k;

    for (i = 0; i < number_of_strings; ++ i)
    {
        cin >> current_string;
        substrings[current_string] = current_string;

        for (j = 1; j <= current_string.length(); ++ j)
        {
            for (k = 0; k <= current_string.length() - j; ++ k)
            {
                current_substr = current_string.substr(k, j);
                substrings[current_substr] = current_substr;
            }
        }
    }

    vector <string> numbered_substrings;

    for (map <string, string>::iterator it = substrings.begin(); it != substrings.end(); ++ it)
        numbered_substrings.push_back(it->second);

    unsigned int number_of_queries = 0;
    unsigned int query = 0;

    cin >> number_of_queries;
    current_string.clear();

    for (i = 0; i < number_of_queries; ++ i)
    {
        cin >> query;
        -- query;

        if ((query >= 0) && (query < numbered_substrings.size()))
            current_string = current_string + numbered_substrings[query] + '\n';
            else
                cout << "INVALID: " << query << '\n' << endl;
    }

    cout << current_string;

    return 0;
}