一些常用算法模板(三)
0; i < 26; i++) { if (s->next[i]) del(s->next[i]); } delete s; s = NULL; } //***************************************************************** AC自动机模板 //************************************************************ const int kind = 26;//视具体情况改动 struct node { node *fail; //失败指针 node *next[kind]; //Tire每个节点的26个子节点（最多26个字母） int count; //是否为该单词的最后一个节点 node() { //构造函数初始化 fail=NULL; count=0; memset(next,NULL,sizeof(next)); } }*q[1000*255]; //队列方便用于bfs构造失败指针，大小应依据Tries图//节点个数而定 int head,tail; //队列的头尾指针 node *Root; //1.建立Tries void insert(char *str,node *root) //建立一颗以root为根节点的不带前缀指针的字典树 { node *p=root; int i=0,index; while(str[i]) { index=str[i]-'A';//视具体情况改动 if(p->next[index]==NULL) p->next[index]=new node(); p=p->next[index]; i++; } p->count=1; } //2.建立前缀指针，形成Tries图 void build_ac_automation(node *root) //在建好的字典树上添加前缀指针，形成Tries图，即ac自动机 { int i; root->fail=NULL; q[head++]=root; while(head!=tail) { node *temp=q[tail++]; node *p=NULL; for(i=0;i
next[i]!=NULL) { if(temp==root) temp->next[i]->fail=root; else { p=temp->fail; while(p!=NULL) { if(p->next[i]!=NULL) { temp->next[i]->fail=p->next[i]; break; } p=p->fail; } if(p==NULL) temp->next[i]->fail=root; } q[head++]=temp->next[i]; } } } } //3.查询母串 int query(node *root,char *s) //有多少种模式串出现在母串str[]中 { int i=0,cnt=0,index,len=strlen(s); node *p=root; while(s[i]) { index=s[i]-'A';//视具体情况改动 while(p->next[index]==NULL && p!=root) p=p->fail; p=p->next[index]; p=(p==NULL) root:p; node *temp=p; while(temp!=root&&temp->count) { cnt+=temp->count; temp->count=0; temp=temp->fail; } i++; } return cnt; } //4.初始化 void init() { head=tail=0; Root=new node; } //************************************************************ 后缀数组 //***************************************************************** const int MAXN=100000+100; char str[MAXN];//待处理字符串 int sa[MAXN];//求得的后缀数组 int wa[MAXN],wb[MAXN],wv[MAXN],wh[MAXN]; int cmp(int *r,int a,int b,int l) { return r[a]==r[b]&&r[a+l]==r[b+l]; } //求后缀数组sa[],下标1到n-1(此处n=strlen(str)+1)有效后缀 //将str的n个后缀从小到大进行排序之后把排好序的后缀的开头位置顺次放入sa中。 //保证Suffix(sa[i])
=0;i--) sa[--wh[x[i]]]=i; for(j=1,p=1;p
=j) y[p++]=sa[i]-j; for(i=0;i
=0;i--) sa[--wh[wv[i]]]=y[i]; for(t=x,x=y,y=t,p=1,x[sa[0]]=0,i=1;i
=midlen)//长度大于等于midlen { lowid=min(lowid,sa[i]); highid=max(highid,sa[i]); if(highid-lowid>=midlen)//且不重叠 flag=true; } } if(flag)Minlen=midlen+1; else Maxlen=midlen-1; } return Maxlen<4 0:Maxlen+1; } //***************************************************************** 4.图论 邻接表建图 //***************************************************** const int MAXN=1000+100; const int INF = 0x3f3f3f3f; int head[MAXN]; int dis[MAXN]; bool visited[MAXN]; int qq[MAXN];//模拟队列 struct node { int to; int next; }Edg[20000+100]; int n,m,tot; void init() { tot=0; memset(head,-1,sizeof(head)); } void add(int a,int b) { Edg[tot].to=b; Edg[tot].next=head[a]; head[a]=tot++; } void BFS(int s) { //queue
qq; //qq.push(s); int front,rear; front=rear=0; qq[front++]=s; int now,i,to; for(i=1;i<=n;i++) { if(i!=s)dis[i]=INF; else dis[i]=0; } visited[s]=true; while(rear
j的有向边就可以了，是左边向右边的匹配 //g没有边相连则初始化为0 //uN是匹配左边的顶点数，vN是匹配右边的顶点数 //调用：res=hungary();输出最大匹配数 //优点：适用于稠密图，DFS找增广路，实现简洁易于理解 //时间复杂度:O(VE) //************************************************************ //顶点编号从0开始的 const int MAXN=510; int uN,vN;//u,v数目 int g[MAXN][MAXN]; int linker[MAXN]; bool visited[MAXN]; bool dfs(int u)//从左边开始找增广路径 { int v; for(v=0;v
dis[j]) temp=dis[k=j]; if(temp==INF)break; visited[k]=1; for(j=1;j<=n;++j) if(!visited[j]&&dis[j]>dis[k]+g[k][j]) dis[j]=dis[k]+g[k][j]; } } //************************************************************ flyod算法 //***************************************************************** int const Max=1001; int a[Max][Max];//存放边的权值 int b[Max];//存放顶点的权值 int nex[Max][Max]; //next[i][j]用来保存i-->j的最短路径中i的最优后即最近的顶点 int N; void floyd() //flyod算法求个顶点间的最短路径长度并记录路径 { int i,j,k,fee; for(i=1;i<=N;i++) for(j=1;j<=N;j++) nex[i][j]=j; for(k=1;k<=N;k++) { for(i=1;i<=N;i++) { if(i==k||a[i][k]==-1) continue; for(j=1;j<=N;j++) { if(a[k][j]==-1||j==k) continue; fee = a[i][k]+a[k][j]+b[k]; if(a[i][j]==-1||a[i][j]>fee) { a[i][j]=fee; nex[i][j]=nex[i][k