สมมติว่าเรามีสองสตริง str1 และ str2 ค้นหาคำนำหน้าทั่วไปที่ยาวที่สุดระหว่างคำเหล่านี้หลังจากดำเนินการเป็นศูนย์หรือมากกว่าในสตริงที่สอง ในแต่ละการดำเนินการ เราสามารถสลับตัวอักษรสองตัวใดก็ได้ ดังนั้นถ้า str1 ="HERE", str2 ="THERE" ผลลัพธ์จะเป็น 4 สตริงที่สองสามารถสร้าง "HERET" ได้โดยเพียงแค่สลับอักขระ ดังนั้นคำนำหน้าที่ยาวที่สุดคือความยาว 4
อย่างที่เราทราบดีว่าเราสามารถสลับกับ str2 เท่านั้น และความยาวของเมทริกซ์ควรขยายให้ใหญ่สุด แนวคิดก็คือให้ข้ามผ่าน str1 และตรวจสอบว่าความถี่ของอักขระปัจจุบันใน str1 เท่ากันหรือน้อยกว่าใน str2 หรือไม่ ถ้าใช่ ให้เลื่อนไปข้างหน้าในสตริง a มิฉะนั้น ให้แยกและพิมพ์ความยาวของส่วนของสตริง str1 ซึ่งตรงกับอักขระในสตริง str2
ตัวอย่าง
#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
