Самая длинная максимальная повторяющаяся подстрока
Подстрока может иметь длину 1,2,3 …
Вопрос, который я пытался решить, заключался в поиске подстроки, которая встречалась максимальное количество раз. Таким образом, это в основном сводилось к поиску персонажа, имеющего максимальную частоту.
Однако я обнаружил, что могу найти самую длинную повторяющуюся подстроку, используя дерево суффиксов в O (n).
Но суффиксное дерево возвращает подстроку, сохраняя длину в качестве приоритета.
Я хотел найти подстроку, которая встречается чаще всего, и из этих подстрок я хочу найти самую длинную.
Например:
In the following string: ABCZLMNABCZLMNABC
A suffix tree will return ABCZLMN as the longest repeating substring.
However, what I am looking for is ABC; as it is the longest out of all the ones having frequency = 3.
Я попытался решить эту проблему путем генерации подстроки между двумя индексами i и j. После этого находим вхождения этих подстрок в каждом случае, используя алгоритм Z, работающий в O (n). Однако общая сложность была O (n ^ 3)
Мой код O (n ^ 3)
map<ll,vector<string>> m;
string s; cin >> s;
for(ll i=0;i<s.length();i++){
string c;
for(ll len=0; i+len<s.length();len++){
c+=s[i+len];
ll z[N];
ll l=0,r=0;
string kk;
for(ll p=0;p<c.length();p++){
kk+=c[p];
}
kk+="#";
for(ll p=0;p<s.length();p++){
kk+=s[p];
}
for(ll k=1;k<kk.length();k++){
if(k>r){
l=r=k;
while(r<c.length()&&kk[r-l]==kk[r])r++;
z[k]=r-l;
r--;
}
else{
ll m=k-l;
if(z[m]<r-k+l)z[k]=z[m];
else{
l=k;
while(r<c.length()&&kk[r-l]==kk[r])r++;
z[k]=r-l;
r--;
}
}
}
ll occ=0;
for(ll n=0;n<kk.length();n++){
if(z[n]==c.length())occ++;
}
m[occ].push_back(c);
}
}
Я не могу найти подходящее решение, чтобы сделать его эффективным.
Пожалуйста, помогите.
Спасибо.
Решение
Отдельный символ считается подстрокой, поэтому максимальная повторяющаяся подстрока должна встречаться с частотой, равной наиболее распространенному символу в строке.
Одним из следствий этого является то, что каждый символ в максимальной повторяющейся подстроке может встречаться в строке только один раз, потому что, если он встречался более одного раза, этот символ сам по себе стал бы максимальной повторяющейся строкой. Например, подстрока «dad» встречается 5 раз в строке «dadxdadydadzdadydad», а подстрока «d» встречается 10 раз.
Они также должны появляться в одном и том же порядке каждый раз (иначе отдельные символы будут иметь более высокую частоту, чем подстрока, и сами будут максимально повторяющейся подстрокой). Они также не могут появляться отдельно от подстроки (иначе они снова станут максимальной повторяющейся подстрокой).
Поэтому максимальная повторяющаяся подстрока должна состоять из подмножества (или всех) одинаково наиболее часто встречающихся символов.
Мы можем легко определить, какие это символы, просто пройдя строку и посчитав их. Мы также можем определить, какие символы появляются в каком порядке, отслеживая, какие символы появляются до и после каждого символа, сохраняя символ, если он всегда один и тот же, и ноль в противном случае. Например, в строке «abcxabcyabczabcyabc» символу «b» всегда предшествует «a», а затем «c»:
string s; cin >> s;
int i, freq[256];
char prev[256], next[256];
for(i = 1; i < 256; i++)
freq[i] = prev[i] = next[i] = 0;
int maxFreq = 0;
for(i = 0; i < s.length(); i++)
{
char c = s[i];
char p = (i == 0) ? 0 : s[i-1];
char n = (i < s.length() - 1) ? s[i+1] : 0;
if(freq[c] == 0) // first time to encounter this character
{
prev[c] = p;
next[c] = n;
}
else // check if it is always preceded and followed by the same characters:
{
if(prev[c] != p)
prev[c] = 0;
if(next[c] != n)
next[c] = 0;
}
// increment frequency and track the maximum:
if(++freq[c] > maxFreq)
maxFreq = freq[c];
}
if(maxFreq == 0)
return 0;
Затем мы можем выполнить итерацию по каждому символу и из тех, которые имеют частоту, равную максимальной частоте, найти длину строки, которую мы можем сформировать, начиная с этого символа, следуя next индексы персонажа:
int maxLen = 0;
int startingChar = 0;
for(i = 1; i < 256; i++)
{
// should have a frequency equal to the max and not be preceded
// by the same character each time (or it is in the middle of the string)
if((freq[i] == maxFreq) && (prev[i] == 0))
{
int len = 1, j = i;
while(next[j] != 0)
{
len++;
j = next[j];
}
if(len > maxLen)
{
maxLen = len;
startingChar = i;
}
}
}
Найдя максимально повторяющуюся подстроку, распечатайте ее:
// print out the maximum length string:
int j = startingChar;
while(j != 0)
{
cout << (char)j;
j = next[j];
}
cout << endl;
Если вам не нравится перебирать эти массивы фиксированного размера или вам нужно поддерживать символы UNICODE и т. Д., Вы можете использовать map от типа символа до структуры, содержащей частоту символа, а также пред и последующие символы.
Другие решения
Других решений пока нет …