字符串的不同子串的数量

Question

我正在解决DISTINCT SUBSTRING(给定一个字符串,我们需要找到其不同子串的总数).我正在使用trie的后缀来解决它.我正在通过测试用例,但是TLE当我提交并且消耗的空间也非常大时4093M.

注意 - >因为总共可以有256个字符,所以我将数组大小设置为257,ascii值作为索引

我现在在想什么:

for(int i=0;i<p;i++){
    string temp = str.substr(i,p-i);
    insert1(root,temp);
}

由于substr()在最坏的情况下可能需要O(n)时间,因此插入函数在最坏的情况下也需要(n)时间,而O(n)用于循环.O(n ^ 3)这让我变得紧张.

所以我想用这样substr()的东西代替

for(int i=0;i<p;i++){
     string *temp = &str[i];
     insert1(root,temp);
}  ///and it is giving me error please suggest here what is the mistake and what to do

这样我就可以节省O(n)时间.

请告诉我如何修改我的trie方法以获得接受.

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

const int alphabetsize = 257;
int cnt=0;
struct trienode{
    struct trienode* children[alphabetsize];
    bool isendofword;
};

struct trienode *getnode(void){
    struct trienode *newnode = new trienode;
    newnode->isendofword = false;
    for(int i=0;i<alphabetsize;i++){
        newnode->children[i]=NULL;
    }
    return newnode;
}
void insert1(struct trienode* root,string &key){
    struct trienode *temp = root;
    for(int i=0;i<key.length();i++){
        int index = key[i];
        if(!temp->children[index]){
            temp->children[index]=getnode();
            cnt++;
        }
        temp = temp->children[index];
    }
    temp->isendofword=true;
}
int main(){
    int t;
    cin>>t;
    while(t--){
        cnt=0;
        string str;
        cin>>str;
        int p = str.length();
        struct trienode* root = getnode();
        for(int i=0;i<p;i++){
            string temp = str.substr(i,p-i);
            insert1(root,temp);
        }
        cout<<cnt<<endl;
    }

}

Answer 1

为了节省空间，请使用std::string_view重用字符串的空间并将它们存储在std::unordered_set容器中。应该足以处理内存浪费的问题。