Я решал DISTINCT SUBSTRING (учитывая строку, нам нужно найти общее количество ее различных подстрок).
Я использую три суффикса для ее решения.
Япрохождение тестовых случаев, но получение 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).Это приводит меня к TLE.
ошибка: не удалось преобразовать 'temp' из 'std :: __ cxx11 :: string * {aka std :: __ cxx11 :: basic_string *}' в 'std ::__cxx11 :: string {aka std :: __ cxx11 :: basic_string} '||| === Сбой сборки: 2 ошибки, 0 предупреждений (0 минут, 0 секунд) === |
Так что я думаюзамените 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) время.
Пожалуйста, скажите мне, как я могу изменить свой подход с использованием трехблоков, чтобы он был принят.
#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;
}
}