এক স্ট্রিং থেকে লংগেস্ট প্যালিনড্রোমিক সাবস্ট্রিং বের করার জন্য মানachers অ্যালগরিদম ব্যবহার করা যায়। প্রতিটি ক্যারেক্টার সিলেক্ট করে, লেফট এবং রাইট পয়েন্টার ব্যবহার করে চেক করা হয় প্যালিনড্রোম আছে কিনা। আরেকটি অ্যারে থাকে ইনফরমেশন স্টোর করতে, সেটি থেকে সহজে প্যালিনড্রোম কত লম্বা তা বের করা যায়। প্রতিটি ক্যারেক্টারের জন্য অ্যারেতে ইনফরমেশন স্টোর হয়। পুরো স্ট্রিং ট্রাভার্স করার পর, তৈরি অ্যারে থেকে লংগেস্ট প্যালিনড্রোমিক সাবসিকোয়েন্স বের করা যায়।
এই অ্যালগরিদমের টাইম কমপ্লেক্সিটি O(n)।
ইনপুট এবং আউটপুট
ইনপুট: স্ট্রিং: "levelup" আউটপুট: Longest palindrome is: level
অ্যালগরিদম
longestPalindrome(text)
ইনপুট - লংগেস্ট প্যালিনড্রোম খুঁজতে টেক্সট
আউটপুট - টেক্সটে লংগেস্ট কমন প্যালিনড্রোম
শুরু
n := text সাইজ
যদি n = 0, তবে
null স্ট্রিং রিটার্ন করুন
n := 2n+1
longPal নামক সাইজ n-এ অ্যারে ডিফাইন করুন
longPal[0] := 0 এবং longPal[1] := 1
centerIndex := 1
rightIndex := 2
right := 0
maxPalLength := 0
maxCenterIndex := 0
start := -1 এবং end := -1, diff := -1
right := 2 থেকে n-1 পর্যন্ত, করুন
left := 2*centerIndex - right
longPal[right] := 0
diff := rightIndex - right
যদি diff > 0, তবে
longPal[right] := minimum(longPal[left], diff)
যতক্ষণ (right + longPal[right]) < n AND (right - longPal[right]) > 0 AND
(right + longPal[right]+1)mod 2 = 0 OR
text[(right + longPal[right] + 1)/2] = text[(right - longPal[right]-1)/2], করুন
longPal[right] 1 বাড়ান
শেষ
যদি longPal[right] > maxPalLength, তবে
maxPalLength := longPal[right]
maxCenterIndex := right
যদি (right + longPal[right]) > rightIndex, তবে
centerIndex := right
rightIndex := right + longPal[right]
শেষ
start := (maxCenterIndex - maxPalLength)/2
end := start + maxPalLength - 1
palindrome = text[start..end] সাবস্ট্রিং
palindrome রিটার্ন করুন
শেষ
উদাহরণ
#include<iostream> using namespace std; int min(int a, int b) { return (a<b)?a:b; } string longestPalindrome(string mainString) { int n = mainString.size(); if(n == 0) return ""; n = 2*n + 1; //নেক্সট পজিশন কাউন্ট করুন int longPal[n]; //লংগেস্ট প্যালিনড্রোম দৈর্ঘ্য স্টোর করার অ্যারে longPal[0] = 0; longPal[1] = 1; int centerIndex = 1; int rightIndex = 2; int right = 0, left; int maxPalLength = 0, maxCenterIndex = 0; int start = -1, end = -1, diff = -1; for (right = 2; right < n; right++) { left = 2*centerIndex-right; //সেন্টার এবং রাইট ব্যবহার করে লেফট পজিশন ক্যালকুলেট করুন longPal[right] = 0; diff = rightIndex - right; if(diff > 0) longPal[right] = min(longPal[left], diff); while ( ((right + longPal[right]) < n && (right - longPal[right]) > 0) && ( ((right + longPal[right] + 1) % 2 == 0) || (mainString[(right + longPal[right] + 1)/2] == mainString[(right - longPal[right] - 1)/2] ))) { longPal[right]++; } if(longPal[right] > maxPalLength) { //ম্যাক্স প্যালিনড্রোম দৈর্ঘ্য maxPalLength = longPal[right]; maxCenterIndex = right; } if (right + longPal[right] > rightIndex) { centerIndex = right; rightIndex = right + longPal[right]; } } start = (maxCenterIndex - maxPalLength)/2; end = start + maxPalLength - 1; string palindrome; for(int i=start; i<=end; i++) palindrome += mainString[i]; return palindrome; } int main(int argc, char *argv[]) { string mainString, palindrome; cout << "Enter String:"; cin >> mainString; palindrome = longestPalindrome(mainString); cout << "Longest palindrome is: " << palindrome << endl; }
আউটপুট
Enter String: levelup Longest palindrome is: level
