Мне нужно найти самую длинную неперекрывающуюся повторяемую подстроку в строке. У меня есть дерево суффиксов и массив суффиксов доступной строки.
Если разрешено перекрытие, ответ тривиален (самый глубокий родительский узел в дереве суффиксов).
Например, для String = "Acaca"
Если перекрытие разрешено, ответом является "aca", но когда перекрытие не допускается, ответом является "ac" или "ca".
Мне нужен только алгоритм или идея высокого уровня.
П.С.: Я пытался, но в Интернете нет четкого ответа.
Генерировать массив суффикса и сортировать в O (nlogn).ps: Существует более эффективный алгоритм, такой как DC3 и алгоритм Ukkonen. Пример:
Строка: ababc
Суффикс-массив:
start-index подстроки | подстрока
0 - ababc
2 - abc
1 - babc
3 - bc
4 - c
сравнивайте каждую из двух последовательных подстрок и получаем общий префикс со следующим ограничением:
Скажем i1 - индекс подстроки ababc ": 0
скажем i2 - индекс подстроки abc ": 2
общий префикс " ab", длина общего префикса len
abs (i1-i2) > len//избегать дублирования
перейти через массив суффикса с решением, и вы получите результат "ababc", который " ab";
Все решение будет запускать O (nlogn)
Однако, будет особый случай: "aaaaa", что это решение не может решить полностью.
Добро пожаловать, чтобы обсудить и подойти к решению O (nlogn), но не O (n ^ 2)
К сожалению, решение, предложенное Перкинсом, не будет работать. Мы не можем переработать наш путь через решения, чтобы найти длинную повторяющуюся непересекающуюся подстроку. Рассмотрим дерево суффиксов для банана: http://en.wikipedia.org/wiki/Suffix_tree. Разветвление "NA" node с "A" в качестве его родителя будет считаться первым, так как оно имеет наибольшую длину и является ветвящимся node. Но его построенная строка "ANA" перекрывается, поэтому она будет отклонена. Теперь следующий node для рассмотрения с "NA", который будет показывать непересекающуюся длину 2, но подстрока "AN" никогда не будет рассмотрена, поскольку она уже была представлена в уже рассмотренной строке ANA. Поэтому, если вы ищете все повторяющиеся непересекающиеся подстроки, или когда вам нужен первый алфавит, вам не повезло.
По-видимому, существует подход, включающий деревья суффиксов, который работает, но более простой подход изложен здесь: http://rubyquiz.com/quiz153.html
Надеюсь, это поможет!
Построив дерево суффиксов, все суффиксы, разделяющие префикс P, будут потомками общего предка в дереве. Сохраняя максимальный и минимальный индекс суффиксов этого под дерева, мы можем гарантировать повторяющуюся непересекающуюся подстроку длиной min (глубина, max-min), где max-min - расстояние между ними, а глубина - это длина их общий префикс. Требуемое значение - node с максимальным значением.
Самое простое решение - это что-то вроде грубой силы. У вас есть алгоритм, чтобы найти самую длинную строку с перекрывающимися допусками, использовать ее, проверить, имеет ли этот ответ перекрытие, если это так, найдите вторую самую длинную, проверьте и посмотрите, имеет ли она перекрытия и т.д. Это уменьшает его до существующего алгоритма поиска, а затем выполняет операцию подсчета регулярных выражений.
Это можно решить, используя результаты, приведенные в разделе "Вычисление самых длинных предыдущих неперекрывающихся факторов" (см. http://dx.doi.org/10.1016/j.ipl.2010.12.005)
Полный код:
#include <bits/stdc++.h>
using namespace std;
int cplen(string a,string b){
int i,to=min(a.length(),b.length());
int ret=0;
for(i=0;i<to;i++){
if(a[i]==b[i])ret++;
else {
return ret;}
}
return ret;
}
int main(){
{
int len,i;
string str;
cin>>str;
len=str.length();
vector<pair<string,int> >vv;
map<char,int>hatbc;
string pp="";
for(i=len-1;i>=0;i--){
hatbc[str[i]]++;
pp=str.substr(i,len-i);
vv.push_back(make_pair(pp,i));
}
if(len==1 || (int)hatbc.size()==len){
printf("0\n");
continue;
}
if(hatbc.size()==1){
printf("%d\n",len/2);
continue;
}
char prev=str[0];
int foo=1,koo=0;
for(i=1;i<len;){
while(str[i]==prev && i<len){i++;foo++;}
prev=str[i];
i+=1;
if(koo<foo)koo=foo;
foo=1;
}
sort(vv.begin(),vv.end());
int ans=0;
ans=koo/2;
for(i=1;i<(int)vv.size();i++){
int j=i-1;
int a=vv[j].second,b=vv[i].second;
string sa=vv[j].first,sb=vv[i].first;
int cpl;
cpl=cplen(sa,sb);
if(abs(a-b)>=cpl)
ans=max(ans,cpl);
}
printf("%d\n",ans);
}
return 0;
}
Сложность: O (n * log (n)) (из-за сортировки)
Мы используем самый длинный общий префикс (LCP) array и массив суффикса для решения этой проблемы в O (n log n) времени.
Массив LCP дает нам самый длинный общий префикс между двумя последовательными суффиксами в массиве суффиксов.
После построения массива LCP и массива суффиксов мы можем выполнить двоичный поиск длины ответа.
Предположим, что строка "acaca $" . Суффикс-массив указан в фрагменте кода в виде таблицы.
<table border="1">
<tr><th>Suffix Array index</th><th>LCP</th><th>Suffix (implicit)</th></tr>
<tr><td>5</td><td>-1</td><td>$</td></tr>
<tr><td>4</td><td>0</td><td>a$</td></tr>
<tr><td>2</td><td>1</td><td>aca$</td></tr>
<tr><td>0</td><td>3</td><td>acaca$</td></tr>
<tr><td>3</td><td>0</td><td>ca$</td></tr>
<tr><td>1</td><td>2</td><td>caca$</td></tr>
</table>Поскольку мне было трудно найти четкое описание работающего алгоритма для получения самых длинных непересекающихся повторных подстрок с использованием дерева суффиксов, я хотел бы поделиться версией, которую я собрал из различных источников.
Алгоритм
Объяснение
Если подстрока S встречается по меньшей мере дважды в S, это общий префикс P двух суффиксов S i и S j, где i и j обозначают их соответствующие начальные позиции в S Следовательно, существует внутренний узел v в дереве суффиксов для S, который имеет два дочерних листа, которые соответствуют i и j, так что сцепление всех меток ребер пути от корня до v равно P.
Самый глубокий такой узел v (с точки зрения длины его соответствующего префикса) отмечает самую длинную, возможно, перекрывающуюся повторную подстроку в S. Чтобы убедиться, что перекрывающиеся подстроки не рассматриваются, мы должны убедиться, что P не длиннее расстояния между Я и Дж.
Поэтому мы рассчитываем минимальный и максимальный индексы i min и i max для каждого узла, которые соответствуют позициям крайнего левого и крайнего правого суффикса S, которые имеют общий префикс. Минимальные и максимальные индексы в узле могут быть легко получены из значений их потомков. (Расчет индексов был бы более сложным, если бы мы искали самые длинные подстроки, которые встречаются не менее k раз, потому что тогда нужно было бы учитывать расстояния всех индексов потомков, а не только двух, которые находятся дальше друг от друга.) Рассматривая только префиксы P, удовлетворяющие i мин + длина (P) ≤ i макс, убедитесь, что P, начинающийся с S i, достаточно короткий, чтобы не перекрываться с суффиксом S J.
Дополнительные заметки