小编aka*_*234的帖子

我正在解决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 …