শর্টেস্ট প্যালিনড্রোম সমস্যা
একটি স্ট্রিং s দেওয়া আছে। এর সামনে অক্ষর যোগ করে এটি প্যালিনড্রোম বানাতে হবে। সম্ভাব্য সবচেয়ে ছোট প্যালিনড্রোম বের করতে হবে।
উদাহরণ: "abcc" → "ccbabcc" (সামনে "ccb" যোগ করা হয়েছে)
সমাধানের পদ্ধতি (KMP / LPS অ্যারে)
s2 = reverse(s)নিনs2 = s + "#" + s2বানান- KMP-এর LPS (Longest Prefix Suffix) অ্যারে বানান
lps.back()=s-এর সাথে মিলে যাওয়া সবচেয়ে বড় প্রিফিক্স যা সাফিক্সও- বাকি অংশটি রিভার্স করে
s-এর সামনে যোগ করুন
C++ কোড উদাহরণ
0) j = lps[j-1];
else i++;
}
}
string extra = s.substr(lps.back(), n - lps.back());
reverse(extra.begin(), extra.end());
return extra + s;
}
};
int main() {
Solution ob;
cout << (ob.shortestPalindrome("abcc"));
return 0;
}
ইনপুট
"abcc"
আউটপুট
ccbabcc
