Tìm tiền tố chung dài nhất sau khi hoán vị chuỗi thứ hai trong C++

Cho str1, str2. Tìm tiền tố chung dài nhất sau khi hoán vị ký tự str2. Ví dụ str1="HERE", str2="THERE" → 4 (str2 thành "HERET").

Đếm tần suất ký tự str2. Duyệt str1, nếu ký tự còn tần suất >0 trong str2 thì tăng độ dài, giảm tần suất; ngược lại dừng.

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

Kết quả

Length of longest common prefix: 4