Изменения

/* преобразует масив count, так что теперь он содержит позиции в массиве suffs с которых необходимо вставлять подстроки, начинающиеся с соответствующих символов */ '''calc_positions'''('''vector''' &count) //''преобразуем масив count''[0] = 0 '''for''' ('''int''' i = 1; i < 2 .. count.size(); ++i)length count[i] += count[i - 1]; '''rotate'''(count, 1); //''сдвигаем * принимает строку, для которой требуется построить суффиксный массив на 1 вправо для удобства работы с индексами'' count[0] = 0; //''теперь он содержит позиции в массиве suffs с которых '' / возвращает суффиксный массив */''необходимо вставлять подстроки, начинающиеся с соответствующих символов'' '''suff_array'''(string &sstr) s += '$'; int alpha_size ALPHABET = 255; //''На нулевом этапе сортируем подстроки длиной 1''нулевая итерация count = '''vectorint''' count([max(alpha_sizeALPHABET, sstr.length())); //''count -- массив для сортировки подсчетом''] '''fill'''(count, 0); '''for''' (ch '''intin''' i = 0; i < s.length(); ++i)str ++count[ord(s[ich])];++ '''calc_positions'''(count); '''vector''' suffs(s.length()); //''suffs будет хранить индексы начал отсортированных подстрок текущей длины suffs = '''int'''[str.length] '''for''' (ch '''intin''' i = 0; i < s.length(); ++i)str suffs[count[ord(s[i])ch]++] = i; //''подстроки длиной 1 отсортированыclasses = '' //'int'разобьем их на классы эквивалентности'' '''vector''' classes(s[str.length());] '''int''' classes_count classesN = 0; '''char''' last_char = '$'; '''for''' (suf '''intin''' i = 0; i < suffs.size(); ++i) '''if''' s[suffs[i]suf] != last_char last_char = s[suffssuf[i]]; classesN++classes_count; classes[suffs[i]suf] = classes_countclassesN; //''нулевой этап завершен''нулевая итерация завершена //''на следующих этапах сортируем подстроки длиной 2 * cur_len = 2^k'' curr_len = 1 '''for''' ('''intwhile''' cur_len = 1; cur_len <= sstr.length(); cur_len *= 2) //''сортируем по второй половине подстроки'' sorted_by2 = '''vectorint''' sorted_by2(s[str.length());] '''for''' ('''int''' i = 0; i < suffs.size(); ++i). str.length

sorted_by2[i] = suffs[i] + sstr.length() - cur_len;

sorted_by2[i] = suffs[i] - cur_len; //''теперь сортируем по первой половине'' //''сортировка устойчивая, значит получим целиком отсортированные подстроки'' '''fill'''(count, 0); '''for''' (by2 '''intin''' i = 0; i < sorted_by2.size() ++i) ++count[classes[sorted_by2[iby2]]];++ '''calc_positions'''(count); '''for''' ('''int''' i = 0; i < s.. str.length(); ++i) suffs[count[classes[sorted_by2[i]]]++] = sorted_by2[i]; //''Подстроки текущей длины отсортированы'' //new_classes = ''переcчитаем классы эквивалентности'' int'''vector''' new_classes(s[str.length()); new_classes[suffs[0]] = 0; classes_count classesN = 0; '''for''' ('''int''' i = 1; i < new_classes0 .. str.size(); ++i) length '''int''' mid1 = (suffs[i] + cur_len) % suffsstr.size();length '''int''' mid2 = (suffs[i-1] + cur_len) % suffsstr.size();length '''if''' (classes[suffs[i]] != classes[suffs[i-1]] || '''or''' classes[mid1] != classes[mid2]) ++classes_count;classesN new_classes[suffs[i]] = classes_count;classesN //''сохраняем новые классы в classes''= new_classes '''copy'''(new_classes, classes);cur_len *= 2 '''return''' suffs;