Search code examples
c++algorithmpalindrome

Comparing strings excluding punctuation and whitespace

I'm making a program to find the larges palindrome in C++ and I need to get the palindromes for the inputted strings ignoring the case, punctuation and whitespace. For example, see the following line:

Confusius say: Madam, I'm Adam.

Here, the largest palindrome is Madam, I'm Adam if you ignore case, punctuation and whitespace.

The program also have to be efficient so as to test strings with 2000 characters in < 1 second. So I have the following code for returning the largest palindrome:

string largestPal(string input_str) {
    string isPal = "";
    string largest = "";

    int j, k;
    for(int i = 0; i < (input_str.length() - 1); ++i) {
        k = i + 1;
        j = i - 1;

        if(j >= 0 && k < (input_str.length())) {
            if(input_str[i] == input_str[j])
                j--;
            else if(input_str[i] == input_str[j])
                k++;
        }

        while(j >= 0 && k < (input_str.length())) {
            if(input_str[j] != input_str[k])
                break;

            else {
                j--;
                k++;
            }

            isPal = input_str.substr(j + 1, k - j - 1);
            if(isPal.length() > largest.length()) {
                largest = isPal;
            }
        }
    }
    return largest;
}

And I tried entering a fully-formatted string (without whitespace, punctuateion and case) as the parameter to this method and have succeeded in getting the output I want. (for example, the previous example returns MADAMIMADAM as the largest palindrome.

The question:

How can I convert this string back to the way it was (with punctuation, whitespace and case)?

OR

How can I test the stripped string directly within the method largestPal, but return the original string (unstrippped) that corresponds to the selected largest palindrome?

Any help greatly appreciated!

Solution

  • The easiest way is to make a table that maps the characters in the stripped string to their original positions in the unstripped string.

    So for example, if the input is "a V, v", your stripped string would be "avv". And your map would be 1,3,6. This indicates that the first character in the stripped string is the first of the unstripped, the next is the third, the next is the sixth. Make this map as you strip the string.

    When you you have your final output, find it in the stripped string. Look up the indexes in the original string for the first and last characters in the stripped string, and then output that range of characters.

    So for "avv" 1,3,6, your stripped output would be "vv". You find the "vv" in "avv" and look up the corresponding indexes and get 3,6 -- so you want to output characters 3-6 inclusive in the original string, or "V, v".