0

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

孔子说：夫人，我是亚当。

在这里，最大的回文是Madam，如果你忽略大小写、标点符号和空格，我是 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，但返回对应于所选最大回文的原始字符串（未剥离的）？

非常感谢任何帮助！

4

3 回答 3

2

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

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

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

因此，对于“avv”1、3、6，您的剥离输出将是“vv”。您在“avv”中找到“vv”并查找相应的索引并得到 3,6——因此您希望输出原始字符串中包含 3-6 的字符，即“V, v”。

于 2012-04-26T08:22:58.887 回答
2

有两种策略：

  • 使用未修改的字符串，使用切片系统和特定比较器
  • 使用规范版本来查找回文，但要记住它们来自哪里

鉴于您选择了第二种策略，剩下的就是记住您在原始字符串中的位置。如果你记住了回文首字母的索引，那么你可以只计算字母来检索原始字符串中的回文。

于 2012-04-26T08:34:26.300 回答
0

搜索回文时，您必须存储字符位置。所以返回值应该是一个位置对，而不是一个字符串。

然后以与剥离字符串时类似的方式处理原始字符串。跳过空格和标点符号，并计算字母以找到开始和结束位置。

于 2012-04-26T08:24:09.627 回答