Номер отдельной подстроки строки - PullRequest
0 голосов
/ 14 февраля 2019

Я решал 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;
    }

}

Ответы [ 2 ]

0 голосов
/ 14 февраля 2019

У меня нет опыта работы с C ++, но ошибка, о которой вы прокомментировали, может быть вызвана различными ожиданиями компилятора относительно типа переменной, которую он получает при обнаружении переменной temp.

Как и у другихотметили в SPOJ и в комментариях, поскольку длина ввода составляет всего 256 символов, вы можете избежать хэширования и подсчета всех вхождений подстроки.

Другой вариант - изучить самую длинную общуюпрефиксы в массиве суффиксов для строки, для которых существуют известные алгоритмы построения.Если мы выполняем итерацию с конца массива суффиксов, разница между текущей длиной суффикса и самым длинным общим префиксом с его соседом справа говорит нам, сколько введено новых отдельных подстрок.

Например:

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
0 голосов
/ 14 февраля 2019

Для экономии места повторно используйте пространство строк с помощью std :: string_view и сохраните их в контейнере std::unordered_set.Должно быть достаточно, чтобы справиться с проблемой потери памяти.

...