إيجاد البادئة المشتركة الطولى

تستخدم هذه الخوارزمية أسلوب فرق تسد في إيجاد البادئة المشتركة الطولى لمجموعة من السلاسل النصية.

مثال:

Input  : {“geeksforgeeks”, “geeks”, “geek”, “geezer”}
Output : "gee"

Input  : {"apple", "ape", "april"}
Output : "ap"

خطوات الخوارزمية

تقسم الخوارزمية مصفوفة السلاسل النصية إلى جزأين، ثم تقسم كل جزء إلى جزأين، وتستمر في تقسيم المصفوفة بهذه الطريقة إلى أنّ تتبقّى سلسلتان نصّيتان في كل مصفوفة. ثم تعيد الخوارزمية البادئة المشتركة الطولى لكلّ سلسلة نصية.

يوضّح الشكل التالي طريقة عمل الخوارزمية على مصفوفة مكوّنة من أربعة سلاسل نصية.

تنفيذ الخوارزمية

تعرض الأمثلة التالية طريقة تنفيذ الخوارزمية في عدد من لغات البرمجة:

• C++‎:

#include<bits/stdc++.h> 
using namespace std; 

// دالة مساعدة لإيجاد البادئة المشتركة الطولى
// في السلسلتين النصيتين المعطاتين
string commonPrefixUtil(string str1, string str2) 
{ 
	string result; 
	int n1 = str1.length(), n2 = str2.length(); 

	for (int i=0, j=0; i<=n1-1&&j<=n2-1; i++,j++) 
	{ 
		if (str1[i] != str2[j]) 
			break; 
		result.push_back(str1[i]); 
	} 
	return (result); 
} 

// تستخدم هذه الدالة أسلوب فرق تسد
// لإيجاد البادئة المشتركة الطولى في مصفوفة السلاسل النصية المعطاة
// تشبه هذه الطريقة خوارزمية الترتيب بالدمج
string commonPrefix(string arr[], int low, int high) 
{ 
	if (low == high) 
		return (arr[low]); 

	if (high > low) 
	{ 
		// هذه العملية مشابهة للعملية
		// (low + hight) / 2
		// ولكنّها تتجنّب حدوث فيضان عند استخدام قيم كبيرة
		int mid = low + (high - low) / 2; 

		string str1 = commonPrefix(arr, low, mid); 
		string str2 = commonPrefix(arr, mid+1, high); 

		return (commonPrefixUtil(str1, str2)); 
	} 
} 

// اختبار الدالتين السابقتين
int main() 
{ 
	string arr[] = {"geeksforgeeks", "geeks", 
					"geek", "geezer"}; 
	int n = sizeof (arr) / sizeof (arr[0]); 

	string ans = commonPrefix(arr, 0, n-1); 

	if (ans.length()) 
		cout << "The longest common prefix is "
			<< ans; 
	else
		cout << "There is no common prefix"; 
	return (0); 
}

• بايثون:

# دالة مساعدة لإيجاد البادئة المشتركة الطولى
# في السلسلتين النصيتين المعطاتين
def commonPrefixUtil(str1, str2): 

	result = "" 
	n1, n2 = len(str1), len(str2) 
	i, j = 0, 0

	while i <= n1 - 1 and j <= n2 - 1: 
	
		if str1[i] != str2[j]: 
			break
		result += str1[i] 
		i, j = i + 1, j + 1
	
	return result 

# تستخدم هذه الدالة أسلوب فرق تسد 
# لإيجاد البادئة المشتركة الطولى في مصفوفة السلاسل النصية المعطاة 
# تشبه هذه الطريقة خوارزمية الترتيب بالدمج
def commonPrefix(arr, low, high): 

	if low == high: 
		return arr[low] 

	if high > low: 
	
		# هذه العملية مشابهة للعملية
		# (low + hight) / 2
		# ولكنّها تتجنّب حدوث فيضان عند استخدام قيم كبيرة
		mid = low + (high - low) // 2

		str1 = commonPrefix(arr, low, mid) 
		str2 = commonPrefix(arr, mid + 1, high) 

		return commonPrefixUtil(str1, str2) 

# اختبار الدالتين السابقتين
if __name__ == "__main__": 

	arr = ["geeksforgeeks", "geeks", 
				"geek", "geezer"] 
	n = len(arr) 
	ans = commonPrefix(arr, 0, n - 1) 

	if len(ans): 
		print("The longest common prefix is", ans) 
	else: 
		print("There is no common prefix")

• جافا:

class GFG { 

// تابع مساعد لإيجاد البادئة المشتركة الطولى
// في السلسلتين النصيتين المعطاتين
	static String commonPrefixUtil(String str1, String str2) { 
		String result = ""; 
		int n1 = str1.length(), n2 = str2.length(); 

		for (int i = 0, j = 0; i <= n1 - 1 && 
				j <= n2 - 1; i++, j++) { 
			if (str1.charAt(i) != str2.charAt(j)) { 
				break; 
			} 
			result += str1.charAt(i); 
		} 
		return (result); 
	} 

// يستخدم هذا التابع أسلوب فرق تسد
// لإيجاد البادئة المشتركة الطولى في مصفوفة السلاسل النصية المعطاة
// تشبه هذه الطريقة خوارزمية الترتيب بالدمج 
	static String commonPrefix(String arr[], int low, int high) { 
		if (low == high) { 
			return (arr[low]); 
		} 

		if (high > low) { 
			// هذه العملية مشابهة للعملية 
			//  (low + hight) / 2
			// ولكنّها تتجنّب حدوث فيضان عند استخدام قيم كبيرة
			int mid = low + (high - low) / 2; 

			String str1 = commonPrefix(arr, low, mid); 
			String str2 = commonPrefix(arr, mid + 1, high); 

			return (commonPrefixUtil(str1, str2)); 
		} 
		return null; 
	} 

// اختبار التابعين السابقين
	public static void main(String[] args) { 
		String arr[] = {"geeksforgeeks", "geeks", 
			"geek", "geezer"}; 
		int n = arr.length; 

		String ans = commonPrefix(arr, 0, n - 1); 

		if (ans.length() != 0) { 
			System.out.println("The longest common prefix is "
					+ ans); 
		} else { 
			System.out.println("There is no common prefix"); 
		} 
	} 
}

تعطي الشيفرات السابقة المخرجات التالية:

The longest common prefix is gee

التعقيد الزمني

لما كانت طريقة التنفيذ تمرّ على جميع السلاسل النصية وتمرّ على جميع الحروف في كل سلسلة نصية، يمكن القول بأنّ التعقيد الزمني لهذه الخوارزمية يبلغ المقدار O(N M)‎ وتمثّل N عدد السلاسل النصية و M طول أطول سلسلة نصية.

تتطلب هذه الخوارزمية إلى O(M Log N)‎ من المساحة الساندة Auxiliary Space وذلك لتخزين السلسلة النصية التي تضمّ البادئة المشتركة الطولى.

مصادر

• صفحة Longest Common Prefix using Divide and Conquer Algorithm في توثيق الخوارزميات في موقع GeeksforGeeks.