c++ - 需要帮助优化查找所有可能子字符串的程序

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/