c - 最长子串回文问题

Question

我觉得我快搞定了，但出于某种原因，我的第二次测试出现了一个较短的回文而不是最长的回文。我已经标记了我认为错误可能来自的地方，但在这一点上我有点不知所措。任何方向将不胜感激!

#include <stdio.h>
#include <string.h>

/*
 *  Checks whether the characters from position first to position last of the string str form a palindrome.
 *  If it is palindrome it returns 1.  Otherwise it returns 0.
 */
int isPalindrome(int first, int last, char *str)
{
    int i;

    for(i = first; i <= last; i++){
        if(str[i] != str[last-i]){
            return 0;
        }
    }
    return 1;
}

/*
 *  Find and print the largest palindrome found in the string str.  Uses isPalindrome as a helper function.
 */
void largestPalindrome(char *str)
{
    int i, last, pStart, pEnd;
    pStart = 0;
    pEnd = 0;
    int result;

    for(i = 0; i < strlen(str); i++){
        for(last = strlen(str); last >= i; last--){
            result = isPalindrome(i, last, str);
            //Possible error area
            if(result == 1 && ((last-i)>(pEnd-pStart))){
                pStart = i;
                pEnd = last;
            }
        }
    }
    printf("Largest palindrome: ");
    for(i = pStart; i <= pEnd; i++)
        printf("%c", str[i]);
    return;
}

/*
 *  Do not modify this code.
 */
int main(void)
{
    int i = 0;
    /* you can change these strings to other test cases but please change them back before submitting your code */
    //str1 working correctly
    char *str1 = "ABCBACDCBAAB";
    char *str2 = "ABCBAHELLOHOWRACECARAREYOUIAMAIDOINEVERODDOREVENNGGOOD";

    /* test easy example */
    printf("Test String 1: %s\n",str1);
    largestPalindrome(str1);

    /* test hard example */
    printf("\nTest String 2: %s\n",str2);
    largestPalindrome(str2);

    return 0;
}

Answer 1

isPalindrome 中的代码无法正常工作，除非 first 为 0。

考虑 isPalindrome(6, 10, "abcdefghhgX"):

• i = 6;
• last - i = 4;
• 比较 str[i](又名 str[6] 又名 'g')与 str[last-i] (又名 str[4] 又名 'e')正在比较应该考虑的范围之外的数据。
• 它应该与 str[10](或者可能是 str[9] 进行比较——取决于 last 是否是最终字符或超出最终字符的字符)。

您需要重新访问该代码。另请注意，您的代码将对每对字符进行两次测试，一次就足够了。我可能会使用两个索引变量，i 和 j，设置为 first 和 last。循环将递增 i 并递减 j，并且仅在 i 小于 j 时继续。

for (int i = first, j = last; i < j; i++, j--)
{
     if (str[i] != str[j])
         return 0;
}
return 1;