字符串hash
很基本的hash题目，现在做这种程度的题10分钟就敲完1A了。整个程序都是模块化的，思路也能很自然地延伸。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 |
#include<cstdio> #include<cstring> #define MAXP 100003 int n,nc,hd[MAXP],el,sl,ans; char s[16000001]; struct E { int i,p; }e[16000000]; inline void adde(int hs,int i) { e[el].i=i; e[el].p=hd[hs]; hd[hs]=el++; } void init() { memset(hd,-1,sizeof hd); el=ans=0; sl=strlen(s); } int bkdr(char *s,char *e) { int hs=0; while(s!=e) hs=(hs*131+*s++)%MAXP; return hs; } int fi(int hs,int i) { int j,k,l; for(l=hd[hs];l!=-1;l=e[l].p) { j=e[l].i; for(k=0;k<n&&s[i+k]==s[j+k];k++); if(k==n) return 1; } return 0; } void solve() { int i,j,k,l; for(i=0;i+n<=sl;i++) { j=bkdr(s+i,s+i+n); if(!fi(j,i)) { adde(j,i); ans++; } } printf("%d\n",ans); } int main() { while(~scanf("%d%d%s",&n,&nc,s)) { init(); solve(); } return 0; } |