KMP和KMP是好朋友
正文索引 [隐藏]
BZOJ 1251: 序列终结者
splay模板题,再写一遍找手感!Wa了一次!splay对无用节点的处理真的很重要!(其实是你自己偷懒没有判断到底存不存在子节点吧!
|
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 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 |
//WNJXYK //while(true) RP++; #include<iostream> #include<cstdio> #include<algorithm> #include<map> #include<set> #include<queue> #include<string> #include<cstring> using namespace std; const int Maxn=50010; int n,m; int k,l,r,v; int id[Maxn]; struct Btree{ int fa; int ch[2]; int val; int max; int siz; int tag; bool rev; }; Btree tree[Maxn]; int root; inline void update(int x){ int l=tree[x].ch[0],r=tree[x].ch[1]; tree[x].siz=tree[l].siz+1+tree[r].siz; tree[x].max=max(tree[x].val,max(tree[l].max,tree[r].max)); } inline void clean(int x){ //printf("%d\n",x); int l=tree[x].ch[0],r=tree[x].ch[1]; if (tree[x].tag){ if (l){ tree[l].max+=tree[x].tag; tree[l].val+=tree[x].tag; tree[l].tag+=tree[x].tag; } if (r){ tree[r].max+=tree[x].tag; tree[r].val+=tree[x].tag; tree[r].tag+=tree[x].tag; } tree[x].tag=0; } if (tree[x].rev){ swap(tree[x].ch[0],tree[x].ch[1]); if (l){ tree[l].rev^=1; } if (r){ tree[r].rev^=1; } tree[x].rev=false; } } inline void rotate(int x,int &k){ int y=tree[x].fa,z=tree[y].fa; int l=(tree[y].ch[1]==x),r=l^1; if (k==y) k=x; else tree[z].ch[tree[z].ch[1]==y]=x; tree[tree[x].ch[r]].fa=y; tree[y].fa=x; tree[x].fa=z; tree[y].ch[l]=tree[x].ch[r]; tree[x].ch[r]=y; update(y); update(x); } inline void splay(int x,int &k){ while(x!=k){ int y=tree[x].fa,z=tree[y].fa; if (y!=k){ if (tree[y].ch[0]==x ^ tree[z].ch[0]==y) rotate(x,k); else rotate(y,k); } rotate(x,k); } } int find(int x,int rank){ clean(x); int l=tree[x].ch[0],r=tree[x].ch[1]; if (tree[l].siz+1==rank) return x; if (tree[l].siz>=rank) return find(l,rank); return find(r,rank-tree[l].siz-1); } inline void add(int l,int r,int val){ int x=find(root,l),y=find(root,r+2); splay(x,root);splay(y,tree[x].ch[1]); int z=tree[y].ch[0]; tree[z].tag+=val; tree[z].val+=val; tree[z].max+=val; } inline void rev(int l,int r){ int x=find(root,l),y=find(root,r+2); splay(x,root);splay(y,tree[x].ch[1]); int z=tree[y].ch[0]; tree[z].rev^=1; } inline int query(int l,int r){ int x=find(root,l),y=find(root,r+2); splay(x,root);splay(y,tree[x].ch[1]); int z=tree[y].ch[0]; return tree[z].max; } int build(int l,int r,int fa){ if (l>r) return 0; int mid=(l+r)/2; int now=id[mid]; tree[now].tag=0; tree[now].rev=false; tree[now].fa=id[fa]; if (l==r){ tree[now].val=tree[now].max=0; tree[now].siz=1; }else{ tree[now].ch[0]=build(l,mid-1,mid); tree[now].ch[1]=build(mid+1,r,mid); update(now); } return now; } inline void print(){ for (int i=1;i<=n;i++){ printf("%d ",tree[find(root,i+1)].val); } printf("\n"); } int main(){ scanf("%d%d",&n,&m); for (int i=1;i<=n+2;i++) id[i]=i; tree[0].max=tree[0].val=-2100000000; tree[0].siz=0; root=build(1,n+2,0); //printf("Root : %d\n",root); for (int i=1;i<=m;i++){ scanf("%d%d%d",&k,&l,&r); //printf("%d %d %d\n",k,l,r); if (k==1) {scanf("%d",&v);add(l,r,v);} if (k==2) rev(l,r); if (k==3) printf("%d\n",query(l,r)); //print(); } return 0; } |
HDU 5147 Sequence II
树状数组!枚举C，顺带统计C前的二元组（A，B），树状数组求（C，D）个数。
|
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 |
//WNJXYK //while(true) RP++; #include<iostream> #include<cstdio> #include<algorithm> #include<map> #include<set> #include<queue> #include<string> #include<cstring> using namespace std; const int Maxn=50010; int num[Maxn]; long long rev[Maxn]; int n; long long sum[Maxn]; long long tot; long long Ans; inline int lowbit(int x){ return x&-x; } inline void add(int x,int val){ for (int i=x;i<=n;i+=lowbit(i)) sum[i]+=val; } inline int get(int x){ int ret=0; for (int i=x;i;i-=lowbit(i)) ret+=sum[i]; return ret; } int solve(){ scanf("%d",&n); Ans=tot=0; memset(sum,0,sizeof(sum)); for (int i=1;i<=n;i++) scanf("%d",&num[i]); for (int i=n;i>=1;i--){ add(num[i],1); rev[i]=n-i+1-get(num[i]); } memset(sum,0,sizeof(sum)); for (int i=1;i<=n;i++){ Ans=Ans+tot*rev[i]; add(num[i],1); tot+=get(num[i]-1); } printf("%I64d\n",Ans); } int T; int main(){ scanf("%d",&T); for (int i=1;i<=T;i++){ solve(); } return 0; } |
HDU 5145 NPY and girls
区间L，R的答案=(R – L -1)! / (II 每个相同数字个数的阶乘)
莫队直接推！
|
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 95 96 |
//WNJXYK //while(true) RP++; #include <cstdio> #include <cstring> #include <algorithm> #include <iostream> #include <string> #include <vector> #include <cmath> #include <queue> #include <map> #include <set> using namespace std; typedef long long LL; const int N=31111; LL t, n, m, num[N], G; const LL mod = 1000000007; struct node { LL l, r, id; }p[N]; LL ans[N], f[N], ff[N], cou[N]; int cmp(node x, node y) { if(x.l / G != y.l / G) return x.l / G < y.l / G; return x.r < y.r ; } LL pow_(LL x, LL y, LL mm) { LL ret = 1; while(y) { if(y&1) { ret *= x; ret %= mm; } y >>= 1; x *= x; x %= mm; } return ret; } void init() { f[0] = ff[0] = 1; for(LL i = 1; i < N; i++) { f[i] = f[i-1] * i; f[i] %= mod; ff[i] = pow_(f[i], mod - 2, mod); // get Inv(); } } void work() { LL tmp = 1; memset(cou, 0, sizeof(cou)); int L = 1, R = 0; for(int i = 1; i <= m; i++) { while(R < p[i].r) { R ++; tmp = tmp * f[cou[num[R]]] % mod; cou[num[R]] ++; tmp = tmp * ff[cou[num[R]]] % mod; } while(R > p[i].r) { tmp = tmp * f[cou[num[R]]] % mod; cou[num[R]] --; tmp = tmp *ff[cou[num[R]]] % mod; R --; } while(L < p[i].l) { tmp = tmp * f[cou[num[L]]] % mod; cou[num[L]] --; tmp = tmp * ff[cou[num[L]]] % mod; L ++; } while(L > p[i].l) { L --; tmp = tmp * f[cou[num[L]]] % mod; cou[num[L]] ++; tmp = tmp * ff[cou[num[L]]] % mod; } ans[p[i].id] = f[R - L + 1] * tmp % mod; } } int main() { init(); scanf("%I64d", &t); while(t--) { scanf("%I64d%I64d", &n, &m); for(int i = 1; i <= n; i++) { scanf("%I64d", &num[i]); } for(int i = 1; i <= m; i++) { scanf("%I64d%I64d", &p[i].l, &p[i].r); p[i].id = i; } G = (int) sqrt(1.0 * n); sort(p+1, p+1+m, cmp); work(); for(int i = 1; i <= m; i++) { printf("%I64d\n", ans[i]); } } return 0; } |
————————————————密封线以下是正文———————————–
POJ 3461 Oulipo
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 53 54 55 56 57 |
//WNJXYK //while(true) RP++; #include<iostream> #include<cstdio> #include<algorithm> #include<map> #include<set> #include<queue> #include<string> #include<cstring> using namespace std; const int Maxn=10010; string pattern,str; int plen,slen; int nxt[Maxn]; inline void getNxt(){ memset(nxt,0,sizeof(nxt)); int i=0,j=-1; nxt[0]=-1; while(i<plen){ if (j==-1 || pattern[i]==pattern[j]){ i++;j++; nxt[i]=j; }else{ j=nxt[j]; } } } int Ans=0; inline void Kmp(){ Ans=0; int i=0,j=0; while(i<slen){ if (j==-1 || str[i]==pattern[j]){ i++;j++; }else{ j=nxt[j]; } if (j==plen){ Ans++; } } } inline void solve(){ cin>>pattern>>str; plen=pattern.length(); slen=str.length(); getNxt(); Kmp(); printf("%d\n",Ans); } int T; int main(){ scanf("%d",&T); for (;T--;)solve(); return 0; } |
POJ 2752 Seek the Name, Seek the Fame
寻找子串即是前缀又是后缀
Ans->nxt[Ans] 依次寻找答案
|
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 |
//WNJXYK //while(true) RP++; #include<iostream> #include<cstdio> #include<algorithm> #include<map> #include<set> #include<queue> #include<string> #include<cstring> using namespace std; const int Maxn=400010; string pattern; int plen; int nxt[Maxn]; inline void getNxt(){ memset(nxt,0,sizeof(nxt)); int i=0,j=-1; nxt[0]=-1; while(i<plen){ if (j==-1 || pattern[i]==pattern[j]){ i++;j++; nxt[i]=j; }else{ j=nxt[j]; } } } vector<int> Ans; int main(){ while(cin>>pattern){ plen=pattern.length(); getNxt(); Ans.clear(); int k=plen; while(k>0){ Ans.push_back(k); k=nxt[k]; } sort(Ans.begin(),Ans.end()); for (int i=0;i<Ans.size();i++) printf("%d ",Ans[i]); printf("\n"); } return 0; } |
POJ 2406 Power Strings
寻找串的最大循环子串
len-nxt[len]为串的最小循环节
|
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 |
//WNJXYK //while(true) RP++; #include<iostream> #include<cstdio> #include<algorithm> #include<map> #include<set> #include<queue> #include<string> #include<cstring> using namespace std; const int Maxn=5000000; string pattern; int plen; int nxt[Maxn]; inline void getNxt(){ memset(nxt,0,sizeof(nxt)); int i=0,j=-1; nxt[0]=-1; while(i<plen){ if (j==-1 || pattern[i]==pattern[j]){ i++;j++; nxt[i]=j; }else{ j=nxt[j]; } } } int main(){ while(cin>>pattern){ if (pattern[0]=='.') return 0; plen=pattern.length(); getNxt(); if (plen%(plen-nxt[plen])==0){ printf("%d\n",plen/(plen-nxt[plen])); }else{ printf("1\n"); } } return 0; } |
POJ 1961 Period
寻找每个子串的最短循环节长度(如果有的话)
枚举子串,然后同上
|
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 |
//WNJXYK //while(true) RP++; #include<iostream> #include<cstdio> #include<algorithm> #include<map> #include<set> #include<queue> #include<string> #include<cstring> using namespace std; const int Maxn=1000010; string pattern; int plen; int nxt[Maxn]; inline void getNxt(){ memset(nxt,0,sizeof(nxt)); int i=0,j=-1; nxt[0]=-1; while(i<plen){ if (j==-1 || pattern[i]==pattern[j]){ i++;j++; nxt[i]=j; }else{ j=nxt[j]; } } } int RT; int main(){ while(cin>>plen>>pattern){ if (plen==0) return 0; RT++; printf("Test case #%d\n",RT); getNxt(); for (int i=1;i<=plen;i++){ if (i%(i-nxt[i])==0 && i/(i-nxt[i])!=1){ printf("%d %d\n",i,i/(i-nxt[i])); } } printf("\n"); } return 0; } |
Count the string
求子串是其本身前缀的个数->DP
|
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 |
//WNJXYK //while(true) RP++; #include<iostream> #include<cstdio> #include<algorithm> #include<map> #include<set> #include<queue> #include<string> #include<cstring> using namespace std; const int Maxn=200010; string pattern; int plen; int Ans; int f[Maxn]; int nxt[Maxn]; inline void getNxt(){ memset(nxt,0,sizeof(nxt)); int i=0,j=-1; nxt[0]=-1; while(i<plen){ if (j==-1 || pattern[i]==pattern[j]){ i++;j++; nxt[i]=j; }else{ j=nxt[j]; } } } int T; int main(){ scanf("%d",&T); for (int RT=1;RT<=T;RT++){ cin>>plen>>pattern; getNxt(); Ans=0; memset(f,0,sizeof(f)); for (int i=1;i<=plen;i++){ f[i]=f[nxt[i]]+1; Ans=(Ans+f[i])%10007; } printf("%d\n",Ans); } return 0; } |
HDU 3746 Cyclic Nacklace
补偿多少个字符成为循环
|
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 |
//WNJXYK //while(true) RP++; #include<iostream> #include<cstdio> #include<algorithm> #include<map> #include<set> #include<queue> #include<string> #include<cstring> using namespace std; const int Maxn=100010; int nxt[Maxn]; string pattern; int plen; inline void getNxt(){ int i=0,j=-1; nxt[0]=-1; while(i<plen){ if (j==-1 || pattern[i]==pattern[j]){ i++;j++; nxt[i]=j; }else{ j=nxt[j]; } } } int T; int main(){ cin.sync_with_stdio(false); cin>>T; for (int i=1;i<=T;i++){ cin>>pattern; plen=pattern.length(); getNxt(); if (nxt[plen]>0 && plen%(plen-nxt[plen])==0){ printf("0\n"); }else{ printf("%d\n",plen-nxt[plen]-plen%(plen-nxt[plen])); } } return 0; } |
HDU 2087 剪花布条
匹配完成重置的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 53 54 55 56 57 58 |
//WNJXYK //while(true) RP++; #include<iostream> #include<cstdio> #include<algorithm> #include<map> #include<set> #include<queue> #include<string> #include<cstring> using namespace std; const int Maxn=100010; int nxt[Maxn]; string pattern; int plen; inline void getNxt(){ int i=0,j=-1; nxt[0]=-1; while(i<plen){ if (j==-1 || pattern[i]==pattern[j]){ i++;j++; nxt[i]=j; }else{ j=nxt[j]; } } } string str; int slen; int Ans=0; inline void Kmp(){ Ans=0; int i=0,j=0; while(i<slen){ if (j==-1 || pattern[j]==str[i]){ i++;j++; }else{ j=nxt[j]; } if (j==plen){ Ans++; j=0; } } } int T; int main(){ cin.sync_with_stdio(false); while(cin>>str>>pattern){ if (str[0]=='#') return 0; slen=str.length(); plen=pattern.length(); getNxt(); Kmp(); cout<<Ans<<endl; } return 0; } |
HDU 2594 Simpsons’ Hidden Talents
最长第一个串的前缀的二个的后缀
拼起来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 |
//WNJXYK //while(true) RP++; #include<iostream> #include<cstdio> #include<algorithm> #include<map> #include<set> #include<queue> #include<string> #include<cstring> using namespace std; const int Maxn=100010; int nxt[Maxn]; string pattern; int plen; inline void getNxt(){ int i=0,j=-1; nxt[0]=-1; while(i<plen){ if (j==-1 || pattern[i]==pattern[j]){ i++;j++; nxt[i]=j; }else{ j=nxt[j]; } } } string str; int slen; int T; int main(){ cin.sync_with_stdio(false); while(cin>>str>>pattern){ if (str[0]=='#') return 0; pattern=str+pattern; slen=str.length(); plen=pattern.length(); getNxt(); int k=plen; while(k>slen || k>(plen-slen)) k=nxt[k]; if (k==0){ printf("0\n"); }else{ for (int i=0;i<k;i++) printf("%c",pattern[i]); printf(" %d\n",k); } } return 0; } |
HDU 4763 Theme Section
同上一题,Ans->nxt[Ans]枚举长度,验证中间是否有符合Ans=nxt[i]
|
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 |
//WNJXYK //while(true) RP++; #include<iostream> #include<cstdio> #include<algorithm> #include<map> #include<set> #include<queue> #include<string> #include<cstring> using namespace std; const int Maxn=1e6+5; int nxt[Maxn]; string pattern; int plen; inline void getNxt(){ int i=0,j=-1; nxt[0]=-1; while(i<plen){ if (j==-1 || pattern[i]==pattern[j]){ i++;j++; nxt[i]=j; }else{ j=nxt[j]; } } } int T; int main(){ cin.sync_with_stdio(false); cin>>T; for (int RT=1;RT<=T;RT++){ cin>>pattern; //cout<<pattern<<endl; plen=pattern.length(); getNxt(); bool flag=false; int k=plen; while(k*3>plen) k=nxt[k]; while(k>0){ for (int i=k*2;i<=plen-k;i++){ if (nxt[i]==k){ flag=true; break; } } if (flag) break; k=nxt[k]; } if (!flag) printf("0\n"); else printf("%d\n",k); } return 0; } |
原文链接：KMP和KMP是好朋友
WNJXYKの博客 版权所有，转载请注明出处。
还没有任何评论，你来说两句吧!