In this homework you're going to solve the subpalindrome problem.
Now, if you took 101, you saw that a palindrome is a string
that reads the same forwards as it does backwards.
R-A-D-A-R. R-A-D-A-R.
We're going to allow palindromes where the case of the letters can be different.
This would be a good palindrome even though there is a capital R here
and a lowercase r there.
Now, some people allow palindromes where the spaces and punctuation don't count.
You can throw them in anywhere. We're not going to allow this.
We're going to only allow cases where there is an exact match.
This would be a palindrome. It has spaces, but they read the same forwards and backwards.
That's a good one, and this would not be a palindrome,
because the space does not occur in the same place forward and backward.
Now you know what palindrome is, but the problem is to find a subpalindrome.
Here is a string. We want to find the longest palindrome.
It turns out that it occurs from here to here.
Now, how would you find that?
There's one obvious way to do it.
It's to try every possible substring,
so try every starting location--here, here, here, and so on--
and every ending location--the string "w" by itself, "wh," "whe,"
then "h" by itself, "he," "her," and so on.
Try every single one and check to see if they're a palindrome.
Now, that would work, but it would be slow.
If there are N characters in the string, then there's N starting locations
and N ending locations, and each of those substrings can have up to N characters.
To check all of them out would be an order N-cubed operation.
There'd be roughly N-cubed checks that you'd have to make to see if two characters are the same.
What we're asking you to do is to come up with a solution that's faster than that
that takes in the worst case, roughly N-squared rather than N-cubed comparisons,
and in most cases will do better.
When I say operations here, what do I count as an operation?
I want you to write your routine so that all you do is pick out characters,
so we pass you in a text and you pick out a character--text sub i, text sub j--
and then you can do anything you want with the characters you pick out.
You can convert them to uppercase to make it easier to compare if they're the same.
You can compare two characters.
All those operations will be free, but we'll be counting how many of these operations you do.
Now the trick is to find a good way to go through the text and look at the characters.
I'm going to tell you a bad way to enumerate through them,
and you're going to have to come up with a good way.
Let's say that we knew that text from i to j is a palindrome.
Maybe that's abcba.
If we then said let's try to expand this text and look at the next two characters,
we could do that test, but we wouldn't have learned anything about whether or not
this is a palindrome given that this is a palindrome.
We'd have to do the whole test all over again.
We haven't gained any advantage from what we know about a partial result
to expand it to a bigger result.
What we want to do is find some way of saying I know something about
a palindrome somewhere in the string, and that's going to help me
more efficiently figure out a bigger piece of the string.
That's what you're being asked to do.
I'm going to call our function longest
A "slice" meaning what I want you to return is the i and j indices of the start and the end,
and j should be one character after the end
so the same conventions that we use normally in Python
such that text[i, j] is the longest palindrome.
Why did I return the indices rather than the text itself?
Because you might be interesting in where in the text the palindrome occurs.
If you have i and j, it's easy to pull out the actual palindrome,
but if I give you the actual palindrome, it's harder to find where it occurs.
Here what I'm doing is making an abbreviation for this function.
"Longest
Now I'm just assigning another variable L to be equal to that.
Now these two refer to the same function.
I can go ahead and do that,
and I can fit more tests on one line by using the shorter name rather than the longer name.
Write your function so that all the tests pass.
Add any other tests you think are useful and make sure you do it through an efficient recurrence relation.