COUTNPALIN 문제에 대해.. Namnamseo [[problem:COUNTPALIN]] 문제를 풀고 있습니다. 옛날에 이 문제 몇번 시도했다가 못풀었는데, 이번에 국제정보올림피아드 겨울학교에서 palindrome O(n)에 찾는 문제가 나왔더라구요. 거기서 풀어서 되게 기뻤는데 왜 여기 와선 못풀고 있지..ㅠㅠ 어쨌든 이게 알고보니까 Manacher's algorithm이라고 하는거더군요? 몰랐는데.. 소스는 밑에 있습니다. ~~~ c++ for(;t--;){ scanf("%d ",&n); buf[0]='#'; i=1; for(j=0;j buf[i]=getchar(); buf[i+1]='#'; i+=2; } n=(n<<1)|1; c=r=0; count=0; for(i=0;i if(i<=c+r){ i_mirr = 2*c - i; if(i+p[i_mirr] == c+r){ for(j=1;i+j=0;j++){ if(buf[i+j]!=buf[i-j]) break; } j--; p[i]=j; c=i; r=j; } else p[i]=min(c+r-i,p[i_mirr]); } else { for(j=1;i+j=0;j++){ if(buf[i+j]!=buf[i-j]) break; } j--; p[i]=j; c=i; r=j; } } printf("%d\n",count); } ~~~ 배열 선언은 int, char 둘다 2,000,000 개 잡은것 뿐인데 왜 RE가 나는지 모르겠습니다 ㅠㅠ 해결방법 있으신분? 12년 전
3개의 댓글이 있습니다. Kureyo i+j 또는 i-j의 범위가 [0,n)을 벗어날 수 있지않을까 싶네요 :P 그리고 코드를 자세히 읽어본건 아니지만, p값이 맞지않게 나올거같네요.. 12년 전 link Namnamseo @Kureyo 그부분 생각을 못해서 고쳐서 다시 내봤는데 잘 안되네요... 참고로 소스 수정했습니다 12년 전 link Namnamseo 아, 파일입출력때문에 시간초과났네요 ㅋㅋㅋㅋㅋ 12년 전 link 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.
Namnamseo
[[problem:COUNTPALIN]] 문제를 풀고 있습니다.
buf[i]=getchar(); buf[i+1]='#'; i+=2;
if(i<=c+r){=0;j++){=0;j++){
옛날에 이 문제 몇번 시도했다가 못풀었는데,
이번에 국제정보올림피아드 겨울학교에서 palindrome O(n)에 찾는 문제가 나왔더라구요.
거기서 풀어서 되게 기뻤는데 왜 여기 와선 못풀고 있지..ㅠㅠ
어쨌든 이게 알고보니까 Manacher's algorithm이라고 하는거더군요? 몰랐는데..
소스는 밑에 있습니다.
~~~ c++
for(;t--;){
scanf("%d ",&n);
buf[0]='#'; i=1;
for(j=0;j
}
n=(n<<1)|1;
c=r=0;
count=0;
for(i=0;i
i_mirr = 2*c - i;
if(i+p[i_mirr] == c+r){
for(j=1;i+j
if(buf[i+j]!=buf[i-j]) break;
}
j--;
p[i]=j;
c=i; r=j;
} else p[i]=min(c+r-i,p[i_mirr]);
} else {
for(j=1;i+j
if(buf[i+j]!=buf[i-j]) break;
}
j--;
p[i]=j;
c=i; r=j;
}
}
printf("%d\n",count);
}
~~~
배열 선언은 int, char 둘다 2,000,000 개 잡은것 뿐인데 왜 RE가 나는지 모르겠습니다 ㅠㅠ
해결방법 있으신분?
12년 전