ধরুন আমাদের দুটি স্ট্রিং আছে 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
