Найти наименьшую общую суперстроку для двух строк

Будем называть суперстрокой такую строку S(X,Y), в которую исходные строки X и Y входят как подпоследовательности символов. Так как суперстроки возможны разные, нас интересует только самая короткая из них, например, для X = "ASTRAL" и Y = "STRING" получится S = "ASTRINGAL", а для X = "IVAN" и Y = "DIVAN" ответ так и будет "DIVAN". Если существует несколько суперстрок одинаковой наименьшей длины, достаточно найти любую из них.

С применением методов динамического программирования можно решить задачу с временной сложностью алгоритма O(N²).

В сущности, мы просто будем итерационно составлять таблицу (матрицу) возможных подстрок размерностью (X.length()+1) x (Y.length()+1). Основные действия программы пояснены в прикреплённом ниже исходнике. Он проверялся в консоли Visual Studio 2015.

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

string superString(string X, string Y) {
 int m = X.length();
 int n = Y.length();
 // dp[i][j] содержит длину самой короткой подпоследовательности
 // для X[0..i-1] и Y[0..j-1] :
 int **dp;
 dp = new int *[m + 1];
 if (!dp) return string("Memory error 1");
 for (int i = 0; i < m + 1; i++) {
  dp[i] = new int[n + 1];
  if (!dp[i]) return string("Memory error 2");
 }
 //Заполним таблицу сверху вниз:
 for (int i = 0; i < m + 1; i++) {
  for (int j = 0; j < n + 1; j++) {
   if (i == 0) dp[i][j] = j;
   else if (j == 0) dp[i][j] = i;
   else if (X[i - 1] == Y[j - 1]) dp[i][j] = 1 + dp[i - 1][j - 1];
   else dp[i][j] = 1 + min(dp[i - 1][j], dp[i][j - 1]);
  }
 }
 //Найдём индекс самой короткой подпоследовательности:
 int index = dp[m][n];
 string str;
 //Начав с правого нижнего угла, "вытащим" символы в выходную строку:
 int i = m, j = n;
 while (i > 0 && j > 0) {
  //Если текущие символы в X и Y совпадают,
  //текущий символ входит в искомую подпоследовательность
  if (X[i - 1] == Y[j - 1]) {
   str.push_back(X[i - 1]);
   i--; j--; index--;
  }

  //Если же они различны,
  else if (dp[i - 1][j] > dp[i][j - 1]) {
   //положить текущий символ из Y в результат
   str.push_back(Y[j - 1]);
   j--; index--;
  }
  else {
   //или положить текущий символ из X в результат
   str.push_back(X[i - 1]);
   i--; index--;
  }
 }

 //Дошли до конца Y - добавили к результату остаток из X:
 while (i > 0) {
  str.push_back(X[i - 1]);
  i--; index--;
 }
 //И наоборот:
 while (j > 0) {
  str.push_back(Y[j - 1]);
  j--; index--;
 }
 reverse(str.begin(), str.end());
 return str;
}

int main() {
 string X = "ASTRAL";
 string Y = "STRING";
 string S = superString(X, Y);
 cout << S;

 cin.get(); return 0;
}

01.03.2019, 14:48 [1320 просмотров]