c++ - 比较不包括标点符号和空格的字符串

Question

我正在编写一个程序来查找 C++ 中的大回文，我需要为输入的字符串获取回文忽略大小写、标点符号和空格。例如，请参阅以下行:

Confusius say: Madam, I'm Adam.

在这里，如果忽略大小写、标点符号和空格，最大的回文是女士，我是亚当。

该程序还必须高效，以便在 < 1 秒内测试包含 2000 个字符的字符串。所以我有以下返回最大回文的代码:

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;
}

我尝试输入一个完全格式化的字符串(没有空格、标点符号和大小写)作为此方法的参数，并成功获得了我想要的输出。 (例如，前面的示例返回 MADAMIMADAM 作为最大的回文。

问题:

如何将这个字符串转换回原来的样子(带有标点符号、空格和大小写)？

或

如何直接在 largestPal 方法中测试剥离后的字符串，但返回对应于所选最大回文的原始字符串(未剥离)？

非常感谢任何帮助!

Answer 1

最简单的方法是制作一个表，将剥离字符串中的字符映射到它们在未剥离字符串中的原始位置。

例如，如果输入是“a V, v”，您的剥离字符串将是“avv”。你的 map 将是 1,3,6。这表明剥离字符串中的第一个字符是未剥离字符串中的第一个，接下来是第三个，接下来是第六个。在剥离字符串时制作这张 map 。

当您获得最终输出时，请在剥离的字符串中找到它。在原始字符串中查找剥离字符串中第一个和最后一个字符的索引，然后输出该范围的字符。

所以对于“avv”1、3、6，你的剥离输出将是“vv”。你在 "avv"中找到 "vv"并查找相应的索引并得到 3,6 -- 所以你想输出原始字符串中包含 3-6 的字符，或 "V, v"。