C++에서 두 번째 문자열에서 스왑을 수행한 후 두 문자열 사이에서 가장 긴 공통 접두사 찾기

두 개의 문자열 str1과 str2가 있다고 가정합니다. 두 번째 문자열에 대해 0개 이상의 작업을 수행한 후 이들 사이에서 가장 긴 공통 접두어를 찾습니다. 각 작업에서 두 ​​글자를 바꿀 수 있습니다. 따라서 str1 ="HERE", str2 ="THERE"이면 출력은 4가 됩니다. 두 번째 문자열은 문자를 교환하여 "HERET"으로 만들 수 있습니다. 따라서 가장 긴 접두사의 길이는 4입니다.

우리는 str2에서만 교환할 수 있다는 것을 알고 있습니다. 그리고 행렬의 길이는 최대화되어야 합니다. 따라서 아이디어는 str1을 탐색하고 str1의 현재 문자 빈도가 str2의 빈도와 같거나 작은지 확인하는 것입니다. 그렇다면 문자열에서 앞으로 이동하고, 그렇지 않으면 문자열 str2에서 문자가 일치하는 문자열 str1 부분의 길이를 중단하고 인쇄합니다.

예시

#include <iostream>
using namespace std;
void longestPrefix(string str1, string str2) {
   int frequency[26]={0};
   int a = str1.length();
   int b = str2.length();
   for (int i=0 ;i<b ; i++) {
      frequency[str2[i] - 97] += 1;
   }
   int c = 0;
   for (int i=0 ;i<a ; i++) {
      if (frequency[str1[i] - 97] > 0){
         c += 1;
         frequency[str1[i] - 97] -= 1;
      } else
      break;
   }
   cout<<"Length of longest common prefix: " << c;
}
int main() {
   string str1="here", str2 = "there";
   longestPrefix(str1, str2);
}

출력

Length of longest common prefix: 4