Следующий палиндром: ошибка сегментации

Question

Я пытаюсь решить проблему Next Palindrome на SPOJ. Вот ссылка на проблему SPOJ
Это мой код проблемы. Я получаю правильные результаты, когда я запускаю его на моей машине в следующих случаях тест:

                 

Это мой код:

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

char k[1000004]; 

int find_palin(char num[]) 
{ 
int len = strlen(num); 
char str1[1000004] = {NULL}; 
char str3[500002] = {NULL}; 
char str2[500002] = {NULL}; 
char rev[500002] ={NULL}; 

if(len%2==0) 
{ 
    int half = (len)/2; 
    int i; 
    int j=0; 

    for(i=1;i<=len-1;++i) 
    { 
     if(num[i]!='0') 
      break; 

     k[i]='0'; 
    } 

    if(i>len-1) 
    { 
     k[0]=num[0]; 
     k[len-1]=num[0]; 
     return 0; 
    } 

    for(i=0;i<half;++i) 
     str1[i] = num[i]; 

    for(i=half;i<len;++i) 
     str3[j++] = num[i]; 

    for(i=0 , j=half-1;i<half;++i,--j) 
    { 
     if(str3[i]>=str1[j]) 
      break; 
     else 
      rev[i]=str1[j]; 
    } 

    if(i>=half) 
    { 
     strcat(str1,rev); 
     for(i=0;i<len;++i) 
      k[i]=str1[i]; 
     return 0; 
    } 
    else 
    { 
     for(i=0;i<half;++i) 
      str3[i] = '0'; 

     if(str1[half-1]!='9') 
      str1[half-1]++; 
     else 
     { 
      for(i=half-1;i>=0;--i) 
      { 
       if(str1[i]=='9') 
        str1[i] = '0'; 
       else 
       { 
        str1[i]++; 
        break; 
       } 
      } 
      if(i<0) 
      { 
       str1[half]='0'; 
       str1[0] = '1'; 
      } 
     } 

     strcat(str1,str3); 
     find_palin(str1); 
    } 
} 
else 
{ 
    int half = (len-1)/2; 
    int i; 
    int j=0; 

    if(len==1) 
    { 
     if(num[0]=='9') 
     { 
      k[0] = '1'; 
      k[1] = '1'; 
      return 0; 
     } 
     k[0] = ++num[0]; 
     return 0; 
    } 

    for(i=1;i<=len-1;++i) 
    { 
     if(num[i]!='0') 
      break; 

     k[i]='0'; 
    } 

    if(i>len-1) 
    { 
     k[0]=num[0]; 
     k[len-1]=num[0]; 
     return 0; 
    } 

    for(i=0;i<half;++i) 
     str1[i] = num[i]; 

    for(i=half+1;i<len;++i) 
     str3[j++] = num[i]; 

    str2[0] = num[half]; 

    for(i=0 , j=half-1;i<half;++i,--j) 
    { 
     if(str3[i]>=str1[j]) 
      break; 
     else 
      rev[i]=str1[j]; 
    } 

    if(i>=half) 
    { 
     strcat(str2 , rev); 
     strcat(str1 , str2); 
     for(i=0;i<len;++i) 
      k[i]=str1[i]; 
     return 0; 
    } 
    else 
    { 
     for(i=0;i<half;++i) 
      str3[i] = '0'; 

     if(str2[0]!='9') 
     { 
      str2[0]++; 
      strcat(str2,str3); 
      strcat(str1,str2); 
      find_palin(str1); 
     } 
     else 
     { 
      str2[0] = '0'; 

      if(str1[half-1]!='9') 
       str1[half-1]++; 
      else 
      { 
       for(i=half-1;i>=0;--i) 
       { 
        if(str1[i]=='9') 
         str1[i] = '0'; 
        else 
        { 
         str1[i]++; 
         break; 
        } 
       } 
       if(i<0) 
       { 
        str1[half]='0'; 
        str1[0] = '1'; 
       } 
      } 

      strcat(str2,str3); 
      strcat(str1,str2); 
      find_palin(str1); 
     } 
    } 
} 
} 

int main() 
{ 
char input[1000004]; 
int t; 

scanf("%d" , &t); 

int i; 

for(i=0;i<t;++i) 
{ 
    scanf("%s" , &input); 
    find_palin(input); 
    printf("%s\n" , k); 
} 
return 0; 
} 

Когда я пытаюсь представить код, он дает ошибку сегментации. Может кто-то, пожалуйста, помогите мне, почему я получаю эту ошибку?

Answer 1

Способ использования больших массивов состоит в том, чтобы выделить память на heap not on the stack. Я сделал это в вашей программе, чтобы показать вам. Вместо этого в main я лениво переместил input[] как глобальный var. Вы не можете сделать это в find_palin из-за рекурсии, и в любом случае глобальные переменные нахмурились.

Я также изменил все ваши заявления return 0 на goto, чтобы можно было выполнить общую очистку. Это не изящно, но я не хотел менять структуру вашего кода.

Я также подделал несколько других вещей, таких как проверка ввода была действительной и с использованием единственного #define, из которого были получены все другие размеры.

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

#define ARRSIZE 1000004     // don't hard code stuff 

char k[ARRSIZE]; 
char input[ARRSIZE];     // move out of main 

void find_palin(char num[])    // change return type to void 
{ 
    int len = strlen(num); 
    char *str1 = calloc(ARRSIZE, sizeof(*str1)); // allocate and zero 
    char *str2 = calloc(ARRSIZE/2, sizeof(*str2)); 
    char *str3 = calloc(ARRSIZE/2, sizeof(*str3)); 
    char *rev = calloc(ARRSIZE/2, sizeof(*rev)); 
    if (str1 == NULL || str2 == NULL || str3 == NULL || rev == NULL) 
     exit (1);      // check memory allocations 

    if(len%2==0) 
    { 
     int half = (len)/2; 
     int i; 
     int j=0; 

     for(i=1;i<=len-1;++i) 
     { 
      if(num[i]!='0') 
       break; 

      k[i]='0'; 
     } 

     if(i>len-1) 
     { 
      k[0]=num[0]; 
      k[len-1]=num[0]; 
      goto endfunc;    // replace all return statements 
     } 

     for(i=0;i<half;++i) 
      str1[i] = num[i]; 

     for(i=half;i<len;++i) 
      str3[j++] = num[i]; 

     for(i=0 , j=half-1;i<half;++i,--j) 
     { 
      if(str3[i]>=str1[j]) 
       break; 
      else 
       rev[i]=str1[j]; 
     } 

     if(i>=half) 
     { 
      strcat(str1,rev); 
      for(i=0;i<len;++i) 
       k[i]=str1[i]; 
      goto endfunc; 
     } 
     else 
     { 
      for(i=0;i<half;++i) 
       str3[i] = '0'; 

      if(str1[half-1]!='9') 
       str1[half-1]++; 
      else 
      { 
       for(i=half-1;i>=0;--i) 
       { 
        if(str1[i]=='9') 
         str1[i] = '0'; 
        else 
        { 
         str1[i]++; 
         break; 
        } 
       } 
       if(i<0) 
       { 
        str1[half]='0'; 
        str1[0] = '1'; 
       } 
      } 

      strcat(str1,str3); 
      find_palin(str1); 
     } 
    } 
    else 
    { 
     int half = (len-1)/2; 
     int i; 
     int j=0; 

     if(len==1) 
     { 
      if(num[0]=='9') 
      { 
       k[0] = '1'; 
       k[1] = '1'; 
       goto endfunc; 
      } 
      k[0] = ++num[0]; 
      goto endfunc; 
     } 

     for(i=1;i<=len-1;++i) 
     { 
      if(num[i]!='0') 
       break; 

      k[i]='0'; 
     } 

     if(i>len-1) 
     { 
      k[0]=num[0]; 
      k[len-1]=num[0]; 
      goto endfunc; 
     } 

     for(i=0;i<half;++i) 
      str1[i] = num[i]; 

     for(i=half+1;i<len;++i) 
      str3[j++] = num[i]; 

     str2[0] = num[half]; 

     for(i=0 , j=half-1;i<half;++i,--j) 
     { 
      if(str3[i]>=str1[j]) 
       break; 
      else 
       rev[i]=str1[j]; 
     } 

     if(i>=half) 
     { 
      strcat(str2 , rev); 
      strcat(str1 , str2); 
      for(i=0;i<len;++i) 
       k[i]=str1[i]; 
      goto endfunc; 
     } 
     else 
     { 
      for(i=0;i<half;++i) 
       str3[i] = '0'; 

      if(str2[0]!='9') 
      { 
       str2[0]++; 
       strcat(str2,str3); 
       strcat(str1,str2); 
       find_palin(str1); 
      } 
      else 
      { 
       str2[0] = '0'; 

       if(str1[half-1]!='9') 
        str1[half-1]++; 
       else 
       { 
        for(i=half-1;i>=0;--i) 
        { 
         if(str1[i]=='9') 
          str1[i] = '0'; 
         else 
         { 
          str1[i]++; 
          break; 
         } 
        } 
        if(i<0) 
        { 
         str1[half]='0'; 
         str1[0] = '1'; 
        } 
       } 

       strcat(str2,str3); 
       strcat(str1,str2); 
       find_palin(str1); 
      } 
     } 
    } 

endfunc:         // free the memory 
    free(rev); 
    free(str3); 
    free(str2); 
    free(str1); 
} 

int main() 
{ 
    int t; 
    int i; 

    if (1 != scanf("%d" , &t))    // check garbage input 
     exit (1); 
    for(i=0;i<t;++i) 
    { 
     if (1 != scanf("%s" , input))  // remove & 
      exit (1);      // check garbage input 
     find_palin(input); 
     printf("%s\n" , k); 
    } 
    return 0; 
}