roboforum.ru

"наступила весна" и "расцвели подснежники" программа выводит "НЕ"

Код: Выделить всё

Dim T1 As String, T2 As String, MaxT As String, Len1 As Long, Len2 As Long

Private Sub Main()
T1 = "наступила весна"
T2 = "расцвели подснежники"
Len1 = Len(T1)
Len2 = Len(T2)

Perebor "", 0, 0
Print MaxT
End Sub

Sub Perebor(ByVal Combination As String, N1 As Long, N2 As Long)
Dim I As Long, Nn As Long, Ss As String

For I = N1 + 1 To Len1
    Ss = Mid(T1, I, 1)
    Nn = FindN(N2 + 1, Ss)
    If Nn > 0 Then
        Perebor Combination + Ss, I, Nn
    Else
        If Len(Combination) > Len(MaxT) Then MaxT = Combination
    End If
Next I
End Sub

Function FindN(ByVal n As Long, Buka As String)
FindN = InStr(n, T2, Buka)
End Function


социологией и экономикой

Будем решать эту задачу методом динамического программирования. Для этого опишем подзадачи, на которые мы будем разбивать нашу задачу. Мы напишем функцию LCS(p, q), которая находит длину НОП для двух начальных участков a1, …, ap и b1, …, bq наших последовательностей. Пусть для всех пар q и p (p < n, q < m), мы задачу решать уже научились. Попробуем вычислить LCS(n, m). Рассмотрим два случая:


1) an= bm. Тогда LCS(n, m)=LCS(n-1, m-1)+1.


2) an≠ bm. Тогда LCS(n, m)=max(LCS(n, m-1), LCS(n-1, m)).


Пользуясь этими формулами, мы можем заполнить таблицу значений LCS(p, q) для всех p и q последовательно: сначала заполняем первую строчку слева направо, затем вторую и т.д. Последнее число в последней строке и будет ответом на поставленную задачу.


Данный алгоритм требует порядка O(nm) операций.

для быстроты надо удалить все буквы которые встречаются один раз

Код: Выделить всё

#include <iostream>
#include <conio.h>
using namespace std;
int main() {
char a[50];
char b[50];
cin>>a;
cin>>b;
int max_len[50][50];
for(int i = strlen(a) - 1; i >= 0; i--)
      {
         for(int j = strlen(b) - 1; j >= 0; j--)
         {
            if(a[i] == b[j])
            {
               max_len[i][j] = 1 + max_len[i+1][j+1];
            }
            else
            {
               max_len[i][j] = max(max_len[i+1][j], max_len[i][j+1]);
            }
         }
      }
      char res[50];
      int k=0;
      for(int i = 0, j = 0; max_len[i][j]!=0 && i<strlen(a) && j<strlen(b); )
      {
         if(a[i] == b[j])
         {
            res[k]=a[i];
            k++;
            i++;
            j++;
         }
         else
         {
            if(max_len[i][j] == max_len[i+1][j])
               i++;
            else
               j++;
         }
      }

cout<<res<<endl;
getch();
}