Tìm tiền tố chung dài nhất giữa hai chuỗi sau khi thực hiện hoán đổi trên chuỗi thứ hai trong C ++

Giả sử chúng ta có hai chuỗi str1 và str2. Tìm tiền tố chung dài nhất giữa chúng sau khi thực hiện không hoặc nhiều thao tác trên chuỗi thứ hai. Trong mỗi thao tác, chúng ta có thể hoán đổi hai chữ cái bất kỳ. Vì vậy, nếu str1 =“HERE”, str2 =“THERE”, thì kết quả đầu ra sẽ là 4. Chuỗi thứ hai có thể được tạo thành “HERET” bằng cách hoán đổi các ký tự. Vì vậy, tiền tố dài nhất có độ dài 4.

Như chúng ta biết rằng chúng ta chỉ có thể hoán đổi trên str2. Và độ dài của ma trận nên được tối đa hóa. Vì vậy, ý tưởng là duyệt qua str1 và kiểm tra xem tần số của ký tự hiện tại trong str1 có giống hay ít hơn tần số trong str2 hay không. Nếu có, hãy chuyển tiếp trong chuỗi a, nếu không thì ngắt và in độ dài của một phần của chuỗi str1, đến đó một ký tự được khớp trong chuỗi str2.

Ví dụ

#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);
}

Đầu ra

Length of longest common prefix: 4