//8.Имеется 2 строки символов A и B, например, AAABAB и ABAABBB.
//Алгоритм просматривает пару строк и имеет право выполнить одну из команд
//(удалить очередной символ первой (второй) строки, вставить символ A(B) в текущую позицию первой (второй) строки.
//Определить минимальную последовательность команд для преобразования строк.
#include "stdafx.h"
#include <iostream>
#include <algorithm>
using namespace std;
char cur[10];
char removestr(char str[])
{
for (int i = 0; str[i-1] != '\0'; i++)
{
str[i] = str[i + 1];
}
return *str;
}
char *rec(char *str1, char *str2, int i, int maxlen)
{
if ((str1 == '\0') || (str2 == '\0') || i == maxlen)
{
//cout << "String is not found" << endl;
return 0;
}
if (str1[0] == str2[0])
{
cur[i] = str1[0];
rec(str1+1, str2+1, i + 1, maxlen);
}
if (str1[0] != str2[0])
{
if (strlen(str1) > strlen(str2))
{
removestr(str1);
}
else
{
removestr(str2);
}
rec(str1, str2, i, maxlen);
}
if (strcmp(str1, str2) == 0) return str1;
return cur;
}
int main()
{
char string1[] = "AAA";
char string2[] = "ABA";
int maxlen = max(strlen(string1), strlen(string2));
cout << string1 << endl;
cout << string2 << endl;
cout << rec(string1, string2, 0, maxlen) << endl;
system("pause");
}