Самая длинная повторяющаяся без пересечений подстрока в строке

Например, "abra" в "abracadabra", "колокол" в "около колокола околачивались колокольчики", "3" в "333" (иначе будет самопересечение) или пустая в "12345".

Само решение имеет сложность по времени O(N²) - а как меньше? - и использует дополнительную целочисленную таблицу Table размерностью (n+1)x(n+1) при длине строки n символов. Значение Table[i][j] хранит длину совпадающих и не пересекающихся подстрок, ограниченных символами с номерами i и j.

Ниже показан листинг, проверенный в консоли Studio 2019.

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

string longestSubstring(string str) {
 int n = str.length();
 int **Table = new int * [n+1];
 if (!Table) return NULL;
 for (int k=0; k<n+1; k++) {
  Table[k] = new int [n+1];
  if (!Table[k]) return NULL;
  for (int j=0; j<n+1; j++) Table[k][j] = 0;
 }
 string res = ""; int res_length = 0; //строка с результатом и ее длина
 int i, index = 0;
 for (i = 1; i <= n; i++) {
  for (int j = i + 1; j <= n; j++)  {
   if (str[i - 1] == str[j - 1] && Table[i - 1][j - 1] < (j - i)) {
    Table[i][j] = Table[i - 1][j - 1] + 1;
    if (Table[i][j] > res_length) {
     res_length = Table[i][j];
     index = max(i, index);
    }
   }
   else
   Table[i][j] = 0;
  }
 }
 if (res_length > 0)
  for (i = index - res_length + 1; i <= index; i++)
   res.push_back (str[i - 1]);
 for (int k = n; k > -1; k--) delete Table[k];
 delete Table;
 return res;
}
 
int main() {
 string str = "okolokolokolakolokolilosololo";
 string res = longestSubstring(str);
 cout << "Answer is: " << res << ", length = " << res.length();
 cin.get();
 return 0;
}

08.12.2019, 13:18 [1184 просмотра]