kmp算法 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 /* kmp */ #include<iostream> #include<cstdio> #include<cstring> #include<cstdlib> #include<string> using namespace std; int nxt[1003],len1,len2; char s1[1000003],s2[1003]; void initNxt() { nxt[0]=-1; int j=-1; for(int i=1;i<=len2-1;++i) { while(j!=-1&&s2[i]!=s2[j+1]) j=nxt[j]; if(s2[i]==s2[j+1])++j; nxt[i]=j; } } void findApr() { int i,j; for(i=0,j=-1;i<=len1-1;++i) { while(j!=-1&&s1[i]!=s2[j+1]) j=nxt[j]; if(s1[i]==s2[j+1])++j;//find the same if(j==len2-1) { printf("%d\n",i-j+1); } } } int main() { freopen("kmp.in","r",stdin); //freopen("kmp.out","w",stdout); scanf("%s %s",s1,s2); len1=strlen(s1),len2=strlen(s2); initNxt(); findApr(); for(int i=0;i<=len2-1;++i) { printf("%d ",nxt[i]+1); } printf("\n"); return 0; }

计算几何 ! 这部分笔记还不完整。 部分例题 hdu1348 Wall 有一个光源和N 个镜子，问是否存在射出角度使得可以使其接触的前N 面镜子恰好是这N 面镜子的排列 N <=10 hdu1392 Surround the Trees(凸包) poj1654 Area

字符串哈希 例题：luogu3370 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 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 #include<iostream> #include<cstring> #include<cstdios> #include<string> #include<algorithm> using namespace std; const int maxn=10005; typedef unsigned long long ULL; char s[maxn]; ULL Base=62; struct Hash { inline Hash(ULL M,ULL d):Mod(M),low(d){} ULL Mod; ULL low; ULL pre[maxn],//pre[i] store hash of s.substr(1,i) Pow[maxn];//Pow[i] store