मान लीजिए हमारे पास दो तार हैं 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