找到最长的回文

Question

我要return最长的回文，比如"civic"return"civic","fawziizw"return"wziizw" 这是我试过的：

int ispalindrome (char str[],int start,int end) {
    int i=0;
    int j=0;
    int counter=0;
    for(i=start; i<strlen(str); i++) {
        if (str[i]==str[end-i]){
            counter++;
        }
    }
    if(counter==i){
        return counter;
    } else 
        return 0;
}

void longestPalindrome(char str[]) {
    int len = strlen(str);
    int i=0;
    int j=0;
    int start=0;
    Int end =0;
    int counter=0;
    int check=0;
    if (strlen(str)-1==1||strlen(str)-1==2) {
        printf("%s",str);
    } else {
        for (i=0; i<len; i++) {
            counter=0;
            for(j=len-1; j>=0; j--) {
                if(str[i]==str[j]) {
                    counter= ispalindrome(str,i,j);
                    if (counter>check&&counter>0) {
                        check=counter;
                        start=i;
                        end=j;
                    }
                }
            }
        }
        for(i=start; i<=end; i++) {
            printf("%c",str[i]);
        }
    }
}

所以它适用于像 "civic" 或 "madam" 这样的回文，但是当我尝试使用 "fawziizw" 时，它 returns "f" 而不是 "wziizw".

Answer 1

太接近了！

在函数 ispalindrome() 中，您错过了最后的字符，因为 start 可能不是 0，而 i 来自 start (> 0) 将 end-i 错过字符串的结尾

int ispalindrome (char str[],int start,int end) {
    int i=0;
    int j=0;
    int counter=0;
    for(i=start; i<strlen(str); i++) {
            if (str[i]==str[end-i]){ // <===== end-i not ok if start>0
                counter++;
        }}
        if(counter==i){
        return counter;}
        else
            return 0; // better to leave whenever it's not a palindrome
    }

我建议使用更简单的版本。我们使用 i 作为 0 的计数器，因为 start 可能是 >0，以便在这种情况下不会错过最后的字符

int ispalindrome (char str[],int start,int end) {
    for(int i=0 ; i < end-start ; i++) { 
          if (str[start+i] != str[end-i]){
                return 0; // <== return 0 if not a palindrome
        }}
     return end - start + 1; 
}

那么它应该会更好用。在下一个函数中，您可以更改

for(j=len-1; j>=0; j--)

至

for(j=len-1; j>i; j--)

以防万一您有兴趣，longestPalindrome 函数

的轻量级版本

void longestPalindrome(char str[]) {
    int len = strlen(str);
    int i,j;
    int tempstart=0;
    int tempend=0;
    int counter;
    int tempcounter=0;
     for (i=0; i<len; i++) {
          for(j=len-1; j>i; j--) { // >i
                counter= ispalindrome(str,i,j);
                if (counter>=tempcounter&&counter>0) {
                     tempcounter=counter;
                     tempstart=i;
                     tempend=j;
                }
          }
     }
     for(i=tempstart; i<=tempend; i++) {
          printf("%c",str[i]);
     }
     printf("\n");
}

基本相同

Answer 2

我做了这个定义长度的，并检查是否有这个长度的子字符串（原始字符串的）是回文。

长度最初等于整个字符串的长度（因此，第一个子字符串实际上是整个原始字符串），并且在每次迭代时减1。所以，第一个找到的回文子串就是最长的回文串。

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

int ispalindrome(char *start, int length){
    int i;
    for(i=0; i < length-1-i; ++i){
        if (start[i] != start[length-1-i]){
            return 0;
        }
    }
    return 1;
}

void longestPalindrome(char str[]) {
    int lenstr, length, i, j;
    lenstr = strlen(str);
    for (length=lenstr; length > 0; --length){
        for(i=0; length+i <= lenstr; ++i){
            if(ispalindrome(str+i, length)){
                for(j=0; j<length; ++j){
                    printf("%c", str[i+j]);
                }
                return;
            }
        }
    }
}

找到最长的回文

find the longest palindrome

c

max

palindrome