NOI的1.7的34:回文子串代码找不到错误

Question

NOI的1.7的34:回文子串代码找不到错误
原题在http://noi.openjudge.cn/ch0107/34/

#include<iostream>
#include<string.h>
int huiwen(char a[]){
    int t=strlen(a)-1,e=1;
    for(int i=0;i<=t-i;i++){    //写一个判断是否为回文的函数 
        if(a[i]!=a[t-i]) e=0;  //是则返回1，不是返回0 
    }
    return e;
}
using namespace std;
int main(){
    char s[500]={0},a[500]={0},b[250][500]={0};   //s用来输入总字符串，a用来承接s的每一小部分，b用来存放回文字符串 
    cin.getline(s,500);
    int i,k,l,I=0;
    for(i=0;i<strlen(s);i++){                //每次先确定开头 
        for(k=0,l=0;k<strlen(s)-i;k++){      //从s[i]开始每个小循环逐渐往后+1 
            a[l++]=s[i+k];                      //给a赋值，从s[i]到s[i+k]
            if(k!=0&&huiwen(a)==1) strcpy(b[I++],a);  //k!=0排除1个字符的情况 
        }
        for(l=0;l<500;l++) a[l]='\0';     //清空a中上个循环留下的字符 
    }
    for(i=0;i<I;i++){
        for(l=0;l<I-1-i;l++){
            if(strlen(b[l])>strlen(b[l+1])) swap(b[l],b[l+1]);
        }
    }
    for(i=0;i<I;i++) cout<<b[i]<<endl;
}

Answer 1

有两个问题：
（1）排序的时候会改变字符串原来的位置，所以每次增加回文串的时候，需要采用插入排序
（2）回文串的个数可能会大于500，比如输入500个a的时候
代码修改如下：

#include <iostream>
#include <string.h>
using namespace std;
typedef struct _datainfo
{
    int len;
    char data[502];
}Hwc;

//插入
void Insert(Hwc a[], char* c, int n)
{
    int len = strlen(c);

    if (n == 0)
    {
        strcpy(a[0].data, c);
        a[0].len = len;
        return;
    }

    if ( len >= a[n-1].len)
    {
        strcpy(a[n].data, c);
        a[n].len = len;
        return;
    }
    for (int i = 0; i < n; i++)
    {
        if (len < a[i].len)
        {
            for (int j = n; j > i; j--)
                a[j] = a[j - 1];
            strcpy(a[i].data, c);
            a[i].len = len;
            break;
        }
    }
}

int huiwen(char a[]) {
    int t = strlen(a) - 1;
    for (int i = 0; i < t; i++, t--) {    //写一个判断是否为回文的函数 
        if (a[i] != a[t])
            return 0;  //是则返回1，不是返回0 
    }
    return 1;
}

int main() {
    char s[502] = { 0 }, a[502] = { 0 };//s用来输入总字符串，a用来承接s的每一小部分，
    Hwc b[2600];   //b用来存放回文字符串 
    cin.getline(s, 502);
    int i, k, l, I = 0;
    for (i = 0; i < strlen(s); i++) {                //每次先确定开头 
        for (k = 0, l = 0; k < strlen(s) - i; k++) {      //从s[i]开始每个小循环逐渐往后+1 
            a[l++] = s[i + k];                      //给a赋值，从s[i]到s[i+k]
            if (k != 0 && huiwen(a) == 1) {
                Insert(b, a, I);
                I++;
            };  //k!=0排除1个字符的情况
        }

        for (l = 0; l < 502; l++) a[l] = '\0';     //清空a中上个循环留下的字符 
    }
    
    for (i = 0; i < I; i++) cout << b[i].data << endl;
    return 0;
}