Следующий палиндром: ошибка сегментации
Я пытаюсь решить проблему следующего палиндрома на SPOJ. Вот ссылка на проблему SPOJ
Это мой код проблемы. Я получаю правильные результаты, когда запускаю его на своем компьютере для следующих тестовых случаев:
9 11
99 101
808 818
Это мой код:
#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;
}
Когда я пытаюсь отправить код, он дает ошибку сегментации. Может кто-нибудь, пожалуйста, помогите мне, почему я получаю эту ошибку?
1 ответ
Решение
Способ использования больших массивов - выделить память в куче, а не в стеке. Я сделал это в вашей программе, чтобы показать вам. Вместо того чтобы делать это в main Я лениво переехал input[] быть глобальным вар. Вы не можете сделать это в 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;
}