Как применить алгоритм самой длинной общей подпоследовательности к большим строкам?
Как применить самую длинную общую подпоследовательность к большим строкам (600000 символов). Есть ли способ сделать это в DP? Я сделал это для более коротких строк.
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
using namespace std;
int dp[1005][1005];
char a[1005], b[1005];
int lcs(int x,int y)
{
if(x==strlen(a)||y==strlen(b))
return 0;
if(dp[x][y]!=-1)
return dp[x][y];
else if(a[x]==b[y])
dp[x][y]=1+lcs(x+1,y+1);
else
dp[x][y]=max(lcs(x+1,y),lcs(x,y+1));
return dp[x][y];
}
int main()
{
while(gets(a)&&gets(b))
{
memset(dp,-1,sizeof(dp));
int ret=lcs(0,0);
printf("%d\n",ret);
}
}
Решение
Вы должны взглянуть на это статья в котором обсуждаются различные вопросы проектирования и реализации. Указывается, что вы можете посмотреть на Алгоритм Хиршберга который находит оптимальные выравнивания между двумя строками, используя расстояние редактирования (или расстояние Левенштейна). Это может упростить количество места, требуемого от вашего имени.
Внизу вы найдете «LCS с эффективным пространством», определенную таким образом как своего рода смешанный / псевдокод, где m длина A а также n длина B:
int lcs_length(char *A, char *B) {
// Allocate storage for one-dimensional arrays X and Y.
for (int i = m; i >= 0; i--) {
for (int j = n; j >= 0; j--) {
if (A[i] == '\0' || B[j] == '\0') {
X[j] = 0;
}
else if (A[i] == B[j]) {
X[j] = 1 + Y[j+1];
}
else {
X[j] = max(Y[j], X[j+1]);
}
}
// Copy contents of X into Y. Note that the "=" operator here
// might not do what you expect. If Y and X are pointers then
// it will assign the address and not copy the contents, so in
// that case you'd do a memcpy. But they could be a custom
// data type with an overridden "=" operator.
Y = X;
}
return X[0];
}
Если ты заинтересован вот бумага о LCS на струнах из больших алфавитов. Найти алгоритм Approx2LCS в разделе 3.2.
Другие решения
Во-первых, используйте подход динамического программирования снизу вверх:
// #includes and using namespace std;
const int SIZE = 1000;
int dp[SIZE + 1][SIZE + 1];
char a[SIZE + 1], b[SIZE + 1];
int lcs_bottomUp(){
int strlenA = strlen(a), strlenB = strlen(b);
for(int y = 0; y <= strlenB; y++)
dp[strlenA][y] = 0;
for(int x = strlenA - 1; x >= 0; x--){
dp[x][strlenB] = 0;
for(int y = strlenB - 1; y >= 0; y--)
dp[x][y] = (a[x]==b[y]) ? 1 + dp[x+1][y+1] :
max(dp[x+1][y], dp[x][y+1]);
}
return dp[0][0];
}
int main(){
while(gets(a) && gets(b)){
printf("%d\n", lcs_bottomUp());
}
}
Обратите внимание, что вам нужно сохранить только 2 строки (или столбцы), один для dp[x] и еще один для dp[x + 1]:
// #includes and using namespace std;
const int SIZE = 1000;
int dp_x[SIZE + 1]; // dp[x]
int dp_xp1[SIZE + 1]; // dp[x + 1]
char a[SIZE + 1], b[SIZE + 1];
int lcs_bottomUp_2row(){
int strlenA = strlen(a), strlenB = strlen(b);
for(int y = 0; y <= strlenB; y++)
dp_x[y] = 0; // assume x == strlenA
for(int x = strlenA - 1; x >= 0; x--){
// x has been decreased
memcpy(dp_xp1, dp_x, sizeof(dp_x)); // dp[x + 1] <- dp[x]
dp_x[strlenB] = 0;
for(int y = strlenB - 1; y >= 0 ; y--)
dp_x[y] = (a[x]==b[y]) ? 1 + dp_xp1[y+1] :
max(dp_xp1[y], dp_x[y+1]);
}
return dp_x[0]; // assume x == 0
}
int main(){
while(gets(a) && gets(b)){
printf("%d\n", lcs_bottomUp_2row());
}
}
Теперь безопасно сменить SIZE в 600000,
Как указала OP, другие ответы занимают слишком много времени, в основном из-за того, что для каждой внешней итерации копируется 600000 символов.
Чтобы улучшить его, можно вместо физического изменения столбца изменить его логически. Таким образом:
int spaceEfficientLCS(std::string a, std::string b){
int i, j, n = a.size(), m = b.size();
// Size of columns is based on the size of the biggest string
int maxLength = (n < m) ? m : n;
int costs1[maxLength+1], costs2[maxLength+1];
// Fill in data for costs columns
for (i = 0; i <= maxLength; i++){
costs1[i] = 0;
costs2[i] = 0;
}
// Choose columns in a way that the return value will be costs1[0]
int* mainCol, *secCol;
if (n%2){
mainCol = costs2;
secCol = costs1;
}
else{
mainCol = costs1;
secCol = costs2;
}
// Compute costs
for (i = n; i >= 0; i--){
for (j = m; j >= 0; j--){
if (a[i] == '\0' || b[j] == '\0') mainCol[j] = 0;
else mainCol[j] = (a[i] == b[j]) ? secCol[j+1] + 1 :
std::max(secCol[j], mainCol[j+1]);
}
// Switch logic column
int* aux = mainCol;
mainCol = secCol;
secCol = aux;
}return costs1[0];
}