Greatest K-Palindrome Substring
Author: Ilham Winata Kurnia
The maximum length of S (|S|) is only 1000 which allow a simple O(n2) solution to pass the test. For each index i in S, find the longest palindrome extension from that position. Simply iterate index i to the left and right until Si-x <> Si+x. Decrease k at that position (it means we change one of those two characters so Si-x = Si+x), and resume the extension until you can’t extend any longer. Remember that there are odd and even palindrome. The overall complexity of this process is O(n2).
The original constrain for this problem is |S| <= 30000, which made the above O(n2) solution won’t work. So, if the constraint were 30000, how to solve the problem? I know two approaches:
- Use Suffix Tree to answer LCE (Longest Common/Palindrome Extension) from any position in O(1). Extend it k times. The overall complexity is O(n . k).
- Use rolling-hash function to answer whether any two substrings are equal in O(1), and find the LCE in O(lg n) using binary-search. Apparently, this is
Booyer-MooreRabin-Karp sting matching algorithm (an approximate algorithm with a very high chance to success). The overall complexity is O(n . lg n . k). This algorithm was suggested by Kurniady.
This problem was solved by 20 teams. The first team to solve this problem is Joy (61).
- Title Page
- Problem A – Anti Brute Force Lock
- Problem B – Bonus Treasure
- Problem C – Panda Land 7: Casino Island
- Problem D – Disjoint Paths
- Problem E – Expert Enough?
- Problem F – Free Parentheses
- Problem G – Greatest K-Palindrome Substring
- Problem H – Hyper-Mod
- Problem I – ICPC Team Strategy
- Problem J – Jollybee Tournament