C++에서 두 문자열의 공통 부분 시퀀스 계산

<시간/>

문자를 포함하는 str1 및 str2라는 두 개의 문자열이 제공되고 작업은 두 문자열에서 공통 부분 시퀀스를 계산하는 것입니다. 아래 프로그램에서 우리는 동적 프로그래밍을 사용하고 있으며 이를 위해서는 동적 프로그래밍이 무엇이며 어떤 문제에 사용할 수 있는지 알아야 합니다.

동적 프로그래밍 접근 방식은 문제를 더 작고 더 작은 가능한 하위 문제로 나누는 분할 정복과 유사합니다. 그러나 분할 정복과 달리 이러한 하위 문제는 독립적으로 해결되지 않습니다. 오히려 이러한 작은 하위 문제의 결과는 유사하거나 겹치는 하위 문제에 대해 기억되고 사용됩니다.

동적 프로그래밍은 문제가 있는 곳에서 사용되며 유사한 하위 문제로 나눌 수 있으므로 결과를 재사용할 수 있습니다. 대부분 이러한 알고리즘은 최적화에 사용됩니다. 내재된 하위 문제를 해결하기 전에 동적 알고리즘은 이전에 해결된 하위 문제의 결과를 조사하려고 시도합니다. 하위 문제의 솔루션을 결합하여 최상의 솔루션을 얻습니다.

그래서 우리는 다음과 같이 말할 수 있습니다 -

Input − string str1 = “abc”
      String str2 = “ab”
Output − count is 3

설명 − 주어진 문자열에서 형성된 공통 부분열은 {'a', 'b' , 'ab'}입니다.

Input − string str1 = “ajblqcpdz”
      String str2 = “aefcnbtdi”
Output − count is 11

일반적인 하위 시퀀스는 − 주어진 문자열에서 형성된 공통 하위 시퀀스는 다음과 같습니다. { "a", "b", "c", "d", "ab", "bd", "ad", "ac", "cd", "abd" , "acd" }

아래 프로그램에서 사용된 접근 방식은 다음과 같습니다.

str1과 str2를 가정해 두 개의 문자열을 입력합니다.
문자열의 문자 수에 따라 정수 값을 반환하는 length() 함수를 사용하여 주어진 문자열의 길이를 계산하고 str1의 경우 len1, str2의 경우 len2에 저장합니다.
arr[len1+1][len2+1]
이라고 가정해 봅시다.
i가 len1보다 작을 때까지 i에 대한 루프 시작
루프 내부에서 j가 len2보다 작을 때까지 j에 대해 다른 루프를 0으로 시작합니다.
루프 내부에서 IF str1[i-1] =str2[j-1]을 확인한 다음 arr[i][j] =1 + arr[i][j-1] + arr[i-1][j]<를 설정합니다. /P>
그렇지 않으면 arr[i][j] =arr[i][j-1] + arr[i-1][j] =arr[i-1][j-1]
을 설정합니다.
반환 arr[len1][len2]
결과를 인쇄하십시오.

예시

#include <iostream>
using namespace std;
// To count the number of subsequences in the string
int countsequences(string str, string str2){
   int n1 = str.length();
   int n2 = str2.length();
   int dp[n1+1][n2+1];
   for (int i = 0; i <= n1; i++){
      for (int j = 0; j <= n2; j++){
         dp[i][j] = 0;
      }
   }
   // for each character of str
   for (int i = 1; i <= n1; i++){
      // for each character in str2
      for (int j = 1; j <= n2; j++){
         // if character are same in both
         // the string
         if (str[i - 1] == str2[j - 1]){
            dp[i][j] = 1 + dp[i][j - 1] + dp[i - 1][j];
         }
         else{
            dp[i][j] = dp[i][j - 1] + dp[i - 1][j] - dp[i - 1][j - 1];
         }
      }
   }
   return dp[n1][n2];
}
int main(){
   string str = "abcdejkil";
   string str2 = "bcdfkaoenlp";
   cout <<"count is: "<<countsequences(str, str2) << endl;
   return 0;
}

예시

위의 코드를 실행하면 다음과 같은 결과가 나옵니다. -

count is: 51