أطول sub-palindrome في سلسلة في Java

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

خوارزمية البحث عن أطول سلسلة متكررة في سلسلة نصية

النقطة المحورية هنا هي أنه من منتصف أي سلسلة متكررة إذا تحركنا إلى اليمين واليسار بمقدار واحد، فإن الحرف سيكون دائمًا نفسه. على سبيل المثال 12321، هنا المنتصف هو 3 وإذا واصلنا التحرك بمقدار واحد في كلا الجانبين، سنحصل على 2 ثم 1. سنستخدم نفس الخوارزمية في برنامجنا جافا للعثور على أطول سلسلة متكررة. ومع ذلك، إذا كان طول السلسلة المتكررة زوجيًا، فإن حجم المنتصف أيضًا زوجي. لذلك يجب علينا التأكد في برنامجنا من التحقق من ذلك أيضًا. على سبيل المثال، 12333321، هنا المنتصف هو 33 وإذا واصلنا التحرك بمقدار واحد في كلا الجانبين، سنحصل على 3 ثم 2 وأخيرًا 1.

برنامج جافا للعثور على أطول سلسلة متكررة في سلسلة نصية

في برنامجنا جافا، سنكرر عبر سلسلة الإدخال بوضعية منتصفية ونتحقق من الحرفين الأيمن والأيسر. سنستخدم متغيرين عامين لحفظ موقع بداية ونهاية النص المتعاكس. يجب أيضًا التحقق مما إذا كان هناك نص متعاكس أطول تم العثور عليه بالفعل حيث يمكن أن يكون هناك عدة نصوص متعاكسة في السلسلة المعطاة. فيما يلي البرنامج النهائي الذي يعمل بشكل جيد لجميع الحالات.

package com.journaldev.util;

public class LongestPalindromeFinder {

	public static void main(String[] args) {
		System.out.println(longestPalindromeString("1234"));
		System.out.println(longestPalindromeString("12321"));
		System.out.println(longestPalindromeString("9912321456"));
		System.out.println(longestPalindromeString("9912333321456"));
		System.out.println(longestPalindromeString("12145445499"));
		System.out.println(longestPalindromeString("1223213"));
		System.out.println(longestPalindromeString("abb"));
	}

	static public String intermediatePalindrome(String s, int left, int right) {
		if (left > right) return null;
		while (left >= 0 && right < s.length()
				&& s.charAt(left) == s.charAt(right)) {
			left--;
			right++;
		}
		return s.substring(left + 1, right);
	}

	// O(n^2)
	public static String longestPalindromeString(String s) {
		if (s == null) return null;
		String longest = s.substring(0, 1);
		for (int i = 0; i < s.length() - 1; i++) {
			 // حالات الأعداد الفردية مثل 121
			String palindrome = intermediatePalindrome(s, i, i);
			if (palindrome.length() > longest.length()) {
				longest = palindrome;
			}
			 // حالات الأعداد الزوجية مثل 1221
			palindrome = intermediatePalindrome(s, i, i + 1);
			if (palindrome.length() > longest.length()) {
				longest = palindrome;
			}
		}
		return longest;
	}

}

يوضح الصورة أدناه نتيجة برنامج جافا لأطول نص متعاكس. يمكننا تحسين الكود المذكور أعلاه عن طريق نقل التحقق من النص المتعاكس وطوله إلى وظيفة منفصلة. ومع ذلك، لقد تركت هذا الجزء لك. 🙂 يرجى إعلامي إذا كان هناك أي تنفيذات أفضل أو إذا فشل في أي حالة.

يمكنك تنزيل كود المثال الكامل من مستودعنا في GitHub.