|
|
back to boardthis program gets WA#10. if you consider this program wrong, say whats wrong. #include <stdio.h> #include <string.h> int n; char s1[500100]; char s2[250100]; const int p1 = 19; const int p2 = 683; int h[250100]; int strstr() { // int n = strlen(s1); int i, t = 0, p = 1; for (i=0;i<n;i++) { t = (t*p1 + s1[i]-33)%p2; p = (p)*p1%p2; } h[0] = t; for (i=1;i<=n;i++) { int v = ((h[i-1]*p1-(s1[i-1]-33)*p)+s1[i+n-1]-33)%p2; if (v<0) v = v+p2; h[i] = v; } // for (i=0;i<n;i++) printf("%d\n",h[i]); t = 0; for (i=0;i<n;i++) t = (t*p1 + s2[i]-33)%p2; for (i=0;i<=n;i++) if (t==h[i]) if (strncmp(s1+i,s2,n)==0) return i; return -1; } int main() { scanf("%d",&n); scanf("%s",s1); scanf("%s",s2); strncpy(s1+n,s1,n); s1[2*n] = 0; int t = strstr(); // printf("%d\n",t-reinterpret_cast<int>(s1)); if (t==-1) printf("-1\n");else printf("%d\n",(n-t)%n); return 0; } if "-33" replace with 131, and p2 replace with "999683" then it get AC, but your test is not correct, or answer why it is so. (i know, bad "russian english") whiwaidontknow is my dirty account :) It is True, I am Prudeav's dirty account :) |
|
|