c++ - 字符串的不同子串数

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) for 循环:O(n^3)。这让我 TLE。

error: could not convert 'temp' from 'std::__cxx11::string* {aka std::__cxx11::basic_string*}' to 'std::__cxx11::string {aka std::__cxx11::basic_string}'| ||=== Build failed: 2 error(s), 0 warning(s) (0 minute(s), 0 second(s)) ===|

所以我想用这样的东西替换 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

我没有使用 C++ 的经验，但你评论的错误似乎源于编译器在遇到变量 temp 时对它接收的变量类型的不同期望。

正如其他人在 SPOJ 和评论中指出的那样，由于输入长度仅为 256 个字符，因此您可以通过暴力哈希和计算所有子字符串的出现次数来逃脱。

另一种选择是检查字符串后缀数组中最长的公共(public)前缀，这两种方法都有已知的构造算法。如果我们从后缀数组的末尾开始迭代，当前后缀长度与最长公共(public)前缀及其右侧邻居之间的差异告诉我们引入了多少新的不同子串。

例如:

01234
CCCCC

suffix array:
01234
43210
CCCCC
 CCCC
  CCC
   CC
    C

i: 4 -> 5 new substrings
i: 3 -> lcp(3,4) = len(3) no new substrings
i: 2 -> lcp(2,3) = len(2) no new substrings
i: 1 -> lcp(1,2) = len(1) no new substrings
i: 0 -> lcp(0,1) = len(0) no new substrings

total: 5 distinct substrings

第二个例子:

01234
ABABA

suffix array:
01234
42031
AAABB
 BBAA
 AA B
  B A
  A

i: 4 -> 4 new substrings
i: 3 -> lcp(3,4) = len(3) no new substrings
i: 2 -> 5 new substrings
i: 1 -> lcp(1,2) = len(1) no new substrings
i: 0 -> lcp(0,1) = len(0) no new substrings

total: 9 distinct substrings