之前一直跳过了字符串, 现在才开始系统地学习, 感觉需要记得模板挺多, 在这里列个知识清单总结一下.
(1)字符串 Hash
就是把字符串 s 视为一个 B(一般 B 取不太大的质数)进制的数, 用一个数组 a 来存 s 的前缀 hash 值, a 用 unsigned long long 自动溢出比较方便.
一个重要的柿子: hash(s[l~r])=hash(s[r])-hash(s[l-1])*B^(r-l+1)
B 的幂要预处理出来.
(2)Manacher
很 NB 的算法, 要花点时间理解.
- #include<iostream>
- #include<cstring>
- #include<vector>
- #include<cstdio>
- #include<algorithm>
- using namespace std;
- int Manacher(string &s){
- string t="$#";
- for(int i=0;i<s.size();++i){
- t+=s[i];
- t+="#";
- }
- vector<int> p(t.size(), 0);
- int Mmid=0,Mlen=0,mx=0,id=0;
- for(int i=1;i<t.size();++i){
- p[i]=mx>i?min(p[id*2-i],mx-i):1;
- while(t[i+p[i]]==t[i-p[i]]) ++p[i];
- if(i+p[i]>mx){
- mx=i+p[i];
- id=i;
- }
- if(p[i]>Mlen){
- Mlen=p[i];
- Mmid=i;
- }
- }
- return Mlen-1;
- //return s.substr((Mmid-Mlen)>>1,Mlen-1);
- }
- int main(){
- int cas=0;
- string s;
- while(1){
- cin>>s;
- if(s=="END") break;
- printf("Case %d: %d\n",++cas,Manacher(s));
- }
- return 0;
- }
- View Code
- (3)KMP
这个算法我起码学了 3 遍, 还是经常忘...
这份代码 s 下标从 1 开始.
- #include<cstdio>
- #include<cstring>
- using namespace std;
- const int N=1005;
- int m,n,next[N];
- char A[N],B[N];
- int main(){
- while(1){
- int ans=0;
- scanf("%s",A+1);
- m=strlen(A+1);
- if(m==1 && A[1]=='#') break;
- scanf("%s",B+1);
- n=strlen(B+1);
- next[1]=0;
- for(int i=2,j=0;i<=n;++i){
- while(j>0 && B[i]^B[j+1]) j=next[j];
- if(B[i]==B[j+1]) ++j;
- next[i]=j;
- }
- for(int i=1,j=1;i<=m;++i){
- while(j>0 && (B[j+1]^A[i] || j==n)) j=next[j];
- if(B[j+1]==A[i]) ++j;
- if(j==n) ++ans,j=0;
- }
- printf("%d\n",ans);
- }
- return 0;
- }
- View Code
(4)最小表示法
某些题目把形如 "abcd","bcda","cdab","dabc" 这些字符串 (其实它们叫循环同构串) 视为同一字符串, 这时我们可以通过求出这些串的最小表示来提高比较和 hash 的效率.
这份模板代码 s 下标从 1 开始.
可以求出 s 的最小表示的起始位置.
- int minpre(char *s){
- int n=strlen(s+1);
- for(int i=1;i<=n;++i) s[n+i]=s[i];
- int i=1,j=2,k;
- while(i<=n && j<=n){
- for(k=0;k<n&&s[i+k]==s[j+k];++k) ;
- if(k==n) break; //s 只由一个字符构成
- if(s[i+k]>s[j+k]){
- i=i+k+1;
- if(i==j) ++i;
- }
- else{
- j=j+k+1;
- if(i==j) ++j;
- }
- }
- return min(i,j);
- }
- View Code
给一道题目: POJ-3349 http://poj.org/problem?id=3349
此题 POJ 上提交时记得选 G++.
- #include<cstdio>
- #include<cctype>
- #include<cstring>
- #include<algorithm>
- using namespace std;
- const int N=1e5+5,P=99991;
- inline int read(){
- int x=0,w=0;char ch=0;
- while(!isdigit(ch)) w|=ch=='-',ch=getchar();
- while(isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
- return w?-x:x;
- }
- int n,tot,tmp[12],snow[N][12],tail[N],last[N],minl[N];
- int minprs(int *a){
- int i=0,j=1,k;
- while(i<6&&j<6){
- for(k=0;k<6&&a[i+k]==a[j+k];++k) ;
- if(k==6) break;
- if(a[i+k]>a[j+k]){
- i=i+k+1;
- if(i==j) ++i;
- }
- else{
- j=j+k+1;
- if(i==j) ++j;
- }
- }
- return min(i,j);
- }
- bool cmp(int pa,int *a,int *b){
- int pb,pc,c[12];
- for(int i=0;i<12;++i) c[11-i]=b[i];
- pb=minprs(b),pc=minprs(c);
- bool ok=true;
- for(int i=0;i<6;++i) if(a[pa+i]^b[pb+i]) ok=false;
- if(ok) return true;
- ok=true;
- for(int i=0;i<6;++i) if(a[pa+i]^c[pc+i]) ok=false;
- if(ok) return true;
- return false;
- }
- int Hash(int *a){
- int sum=0;
- for(int i=0;i<6;++i){
- sum=(sum+a[i])%P;
- //mul=(long long)mul*a[i]%P;
- }
- return sum;
- }
- bool insert(int *a){
- int val=Hash(a);
- for(int p=tail[val];p;p=last[p])
- if(cmp(minl[p],snow[p],a)) return true;
- ++tot;
- for(int i=0;i<12;++i) snow[tot][i]=a[i];
- minl[tot]=minprs(snow[tot]);
- last[tot]=tail[val];
- tail[val]=tot;
- return false;
- }
- int main(){
- n=read();
- for(int i=1;i<=n;++i){
- for(int j=0;j<6;++j) tmp[j]=tmp[j+6]=read();
- if(insert(tmp)){
- puts("Twin snowflakes found.");
- return 0;
- }
- }
- puts("No two snowflakes are alike.");
- return 0;
- }
- View Code
(5)最小循环元
直接上柿子:
1如果 (i-next[i])%i==0, 那么(i-next[i]) 是 s[1~i]的最小循环元长度.
2一个字符串的所有循环元长度都是最小循环元长度的倍数.
3把一个任意的 s 在添加字符最少的情况下补成一个循环同构串 s', 设 s 的长度为 len, 那么有两种情况:
(i)next[i]=0 此时 s 自成 s'的最小循环元, 即需添加 len 个字符才能补成循环同构串.
(ii)next[i]≠0 此时 s'的最小循环元长度为 t=(len-next[len]), 若 (len%t==0),s 就等于 s', 否则最少需添加(t-len%t) 个字符才能补成循环同构串.
(6)Trie
这可能是最好理解的字符串算法之一了.
注意开数组时节点数应为(串的个数 * 串的最长长度).
来个一般的模板:(HDU-1671 http://acm.hdu.edu.cn/showproblem.php?pid=1671 )
- #include<cstdio>
- #include<cctype>
- #include<cstring>
- #include<iostream>
- using namespace std;
- const int N=1e5+5;
- inline int read(){
- int x=0,w=0;char ch=0;
- while(!isdigit(ch)) w|=ch=='-',ch=getchar();
- while(isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
- return w?-x:x;
- }
- struct Trie{
- int tot;
- bool mark[N];
- int node[N][15];
- void reset(){
- tot=0;
- memset(mark,0,sizeof mark);
- memset(node,0,sizeof node);
- }
- bool insert(char *s){
- int p=0;
- int l=strlen(s);
- for(int i=0;i<l;++i){
- int num=s[i]^48;
- if(!node[p][num]) node[p][num]=++tot;
- p=node[p][num];
- if(mark[p]) return false;
- }
- mark[p]=true;
- for(int i=0;i<=9;++i) if(node[p][i]) return false;
- return true;
- }
- }T;
- int t,n;
- char s[10005];
- int main(){
- t=read();
- while(t--){
- T.reset();
- bool fg=0;
- n=read();
- for(int i=1;i<=n;++i){
- scanf("%s",s);
- if(fg) continue;
- if(T.insert(s)) continue;
- else
- fg=1;
- }
- if(fg) puts("NO");
- else puts("YES");
- }
- return 0;
- }
- View Code
稍稍扩展一下, 可以用 Trie 来搞异或和的问题.
看这道题: POJ-3764 http://poj.org/problem?id=3764
建一棵以 0 为根的树, 用 d[i]表示从根节点到节点 i 路径上的异或和, 可以知道对于任意两个节点 i 和 j, 它们之间路径的异或和就等于 d[i]^d[j].
那么问题转化成: 在数组 d 中找两个数, 使它们的异或值最大.
这可以用 Trie 解决. 具体来说, 把每个数视为 32 位的二进制串(不足在高位补 0), 建一棵 01Trie 树, 然后对于每个数, 在 Trie 树中尽量走与它的每一位相反的边(具体看代码).
要注意高位补 0 是如何实现的, 还有节点数应是(数的个数 * 32).
- #include<cstdio>
- #include<cctype>
- #include<cstring>
- #include<algorithm>
- using namespace std;
- const int N=1e5+5;
- inline int read(){
- int x=0,w=0;char ch=0;
- while(!isdigit(ch)) w|=ch=='-',ch=getchar();
- while(isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
- return w?-x:x;
- }
- struct Graph{
- struct Edge{
- int v,w,last;
- }e[N<<1];
- int tot,tail[N];
- void clear(){
- tot=0;
- memset(tail,0,sizeof tail);
- }
- void add(int x,int y,int z){
- e[++tot]=(Edge){y,z,tail[x]};
- tail[x]=tot;
- }
- }G;
- int n,d[N];
- void dfs(int x,int pre){
- for(int p=G.tail[x];p;p=G.e[p].last){
- int v=G.e[p].v,w=G.e[p].w;
- if(v^pre){
- d[v]^=d[x]^w;
- dfs(v,x);
- }
- }
- }
- int tree[N<<5][2],tot;
- void insert(int x){
- int p=1;
- for(int i=30;i>=0;--i){
- int ch=(x>>i)&1;
- if(!tree[p][ch]){
- tree[p][ch]=++tot;
- }
- p=tree[p][ch];
- }
- }
- int search(int x){
- int p=1,ans=0;
- for(int i=30;i>=0;--i){
- int ch=(x>>i)&1;
- if(tree[p][ch^1]) p=tree[p][ch^1],ans|=(1<<i);
- else p=tree[p][ch];
- }
- return ans;
- }
- int main(){
- while(scanf("%d",&n)!=EOF){
- int ans=0;
- G.clear();tot=1;
- memset(d,0,sizeof d);
- memset(tree,0,sizeof tree);
- for(int i=1;i<n;++i){
- int x=read(),y=read(),z=read();
- G.add(x,y,z),G.add(y,x,z);
- }
- dfs(0,-1);
- for(int i=0;i<n;++i){
- ans=max(ans,search(d[i]));
- insert(d[i]);
- }
- printf("%d\n",ans);
- }
- return 0;
- }
- View Code
再扩展一下, 可以解决经典的哈夫曼编码问题, 在此就不说了(这个人太懒了).
(7)AC 自动机
至此, AC 自动机终于揭开了 "自动 AC 题目" 的神秘面纱, 向世人显露真容(滑稽)
与以往想象的不同, 其实 AC 自动机非常好理解也非常好写.
挂一道几乎是模板题的代码: HDU-3695 http://acm.hdu.edu.cn/showproblem.php?pid=3695
- #include<cstdio>
- #include<cstring>
- #include<queue>
- #include<iostream>
- using namespace std;
- const int N=255*1005;
- namespace AC{
- // 根节点是 0
- int mark[N];
- int tree[N][26],fail[N],tot;
- void clear(){
- tot=0;
- memset(mark,0,sizeof mark);
- memset(fail,0,sizeof fail);
- memset(tree,0,sizeof tree);
- }
- void insert(string s){
- int p=0;
- for(int i=0;i<s.size();++i){
- int ch=s[i]-'A';
- if(!tree[p][ch]) tree[p][ch]=++tot;
- p=tree[p][ch];
- }
- ++mark[p];
- }
- void getfail(){
- queue<int> q;
- for(int i=0;i<26;++i)if(tree[0][i]){
- fail[tree[0][i]]=0;
- q.push(tree[0][i]);
- }
- while(!q.empty()){
- int h=q.front();q.pop();
- for(int i=0;i<26;++i)
- if(tree[h][i]){
- fail[tree[h][i]]=tree[fail[h]][i];
- q.push(tree[h][i]);
- }
- else tree[h][i]=tree[fail[h]][i];
- }
- }
- int query(string s){
- int ans=0,p=0;
- for(int i=0;i<s.size();++i){
- p=tree[p][s[i]-'A'];
- for(int j=p;j&&mark[j]^-1;j=fail[j]){
- ans+=mark[j];
- mark[j]=-1;
- }
- }
- return ans;
- }
- };
- void turn(string &s){
- string res;
- int i=0;
- while(i<s.size()){
- if(s[i]^'[') res+=s[i];
- else{
- int num=0;string tmp;
- while(s[i+1]>='0'&&s[i+1]<='9'){
- num=num*10+(s[i+1]^48);
- ++i;
- }
- while(s[i+1]^']'){
- tmp+=s[i+1];
- ++i;
- }
- ++i;
- while(num--) res+=tmp;
- }
- ++i;
- }
- s=res;
- }
- int n,t;
- string s,_s;
- int main(){
- iOS::sync_with_stdio(false);
- cin>>t;
- while(t--){
- int ans=0;
- AC::clear();
- _s.clear();
- cin>>n;
- for(int i=1;i<=n;++i){
- cin>>s;
- AC::insert(s);
- }
- AC::getfail();
- cin>>s;turn(s);
- ans+=AC::query(s);
- for(int i=s.length()-1;i>=0;--i) _s+=s[i];
- ans+=AC::query(_s);
- cout<<ans<<endl;
- }
- return 0;
- }
- View Code
(8)后缀数组
还没学... 留个坑.
来源: http://www.bubuko.com/infodetail-3005413.html