StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>Okay! Here's my second attempt.</p> <p>The idea is that we want to find how many of the characters at the end of the string can be reused when appending the extra characters to complete the palindrome. In order to do this, we will use a modification of the KMP string matching algorithm. Using KMP, we search the original string for its reverse. Once we get to the very end of the string, we will have as much a match as possible between the reverse of the string and the original string that occurs at the end of the string. For example:</p> <pre><code>HELLO O 1010 010 3202 202 1001 1001 </code></pre> <p>At this point, KMP normally would say "no match" unless the original string was a palindrome. However, since we currently know how much of the reverse of the string was matched, we can instead just figure out how many characters are still missing and then tack them on to the end of the string. In the first case, we're missing <code>LLEH</code>. In the second case, we're missing <code>1</code>. In the third, we're missing <code>3</code>. In the final case, we're not missing anything, since the initial string is a palindrome.</p> <p>The runtime of this algorithm is the runtime of a standard KMP search plus the time required to reverse the string: O(n) + O(n) = O(n).</p> <p>So now to argue correctness. This is going to require some effort. Consider the optimal answer:</p> <pre><code> | original string | | extra characters | </code></pre> <p>Let's suppose that we are reading this backward from the end, which means that we'll read at least the reverse of the original string. Part of this reversed string extends backwards into the body of the original string itself. In fact, to minimize the number of characters added, this has to be the largest possible number of characters that ends back into the string itself. We can see this here:</p> <pre><code> | original string | | extra characters | | overlap | </code></pre> <p>Now, what happens in our KMP step? Well, when looking for the reverse of the string inside itself, KMP will keep as long of a match as possible at all times as it works across the string. This means that when the KMP hits the end of the string, the matched portion it maintains will be the longest possible match, since KMP only moves the starting point of the candidate match forward on a failure. Consequently, we have this longest possible overlap, so we'll get the shortest possible number of characters required at the end.</p> <p>I'm not 100% sure that this works, but it seems like this works in every case I can throw at it. The correctness proof seems reasonable, but it's a bit hand-wavy because the formal KMP-based proof would probably be a bit tricky.</p> <p>Hope this helps!</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload