快速认识KMP算法 阮一峰老师带你认识KMP算法 从头到尾彻底理解KMP 浅谈我对KMP中next数组的认识与理解 next数组是因为总是要找失配字符的上一位字符不方便而产生的 next数组的出现使得只用找失配字符对应的next值即为失配字符的上一位字符的最大长度值 根据《最大长度表》，失配时，模式串向右移动的位数 = 已经匹配的字符数 - 失配字符的上一位字符的最大长度值 而根据《next 数组》，失配时，模式串向右移动的位数 = 失配字符的位置 - 失配字符对应的next 值 有上述得匹配的字符数=失配字符的位置，失配字符的上一位字符的最大长度值=失配字符对应的next 值 next数组与最大长度表都是对模式串特征的一种映射，使得不需要像BF算法那样匹配多次，相同部分可以跳过 next数组的第一位为何是-1 由于第一位匹配就失配时，默认向右移动1位，即模式串向右移动的位数=1，此时失配字符的位置=0，代入（模式串向右移动的位数 = 失配字符的位置 - 失配字符对应的next 值）改式之中，即可解得next值为-1 next数组核心代码 //优化过后的next 数组求法 void GetNextval(char* p, int next[]) { int pLen = strlen(p); next[0] = -1; int k = -1; int j = 0; while (j < pLen - 1) { //p[k]表示前缀，p[j]表示后缀 if (k == -1 || p[j] == p[k]) { ++j; ++k; //较之前next数组求法，改动在下面4行 if (p[j] !……

阅读全文

BF算法 BF算法又称朴素的模式匹配算法，属于串匹配中的暴力法 即在S的所有字符中逐个匹配P的每个字符。 局限性 如果情况最坏的时候，假设在一个长度为n的文本串中查找一个长度为m的模式串，则需要匹配n*m次。复杂度将会由O（m+n）退化到O（mn） 核心代码 void BF(string s, string p) { int i = 0, j = 0, count = 0,sum=0,ans=0;//i记录文本串位置，j记录模式串位置，count统计该趟匹配次数,sum统计总判断次数，ans统计匹配轮数 while (i < s.size()) { if (s.at(i) == p.at(j)) {//匹配成功，下一位 i++; j++; count++; sum++; } else {//匹配失败 j回溯，i回滚起始的下一位 i=i-count+1; j = 0; count = 0; sum++; ans++; } if (count == p.size()) { ans++; cout << "模式匹配成功，共走了" << ans << "轮" << endl; cout << "判断了" << sum << "次" << endl; return; } } cout << "匹配失败" << endl; cout << "判断了" << sum << "次" << endl; } ……

阅读全文

什么是BFS BFS又称为广度优先搜索。举个例子：一群老鼠走迷宫。假设老鼠是无限多的，这群老鼠进去后，在每个路口派出部分老鼠探索所有没走过的路。走某条路的老鼠，如果碰壁无法前行，就停下；如果到达的路口已经有其他老鼠探索过了，也停下。很显然，所有的道路都会走到，而且不会重复。这个思路就是BFS。BFS看起来像“并行计算”，不过，由于程序是单机顺序运行的，所以可以把BFS看成是并行计算的模拟。 如何实现BFS 在具体编程时，一般用队列这种数据结构来具体实现BFS，甚至可以说“BFS=队列”。 代码如下： #include<iostream>#include<queue>#define CHECK(x,y)(x>=0&&x<=wx&&y>=0&&y<=hy) using namespace std; int wx,hy,num; char room[23][23]; int dir[4][2]={{-1,0},{0,-1},{1,0},{0,1}}; struct node{ int x,y; } void BFS(int dx,int dy){ num=1; queue<node>q; node start,next; start.x=dx; start.y=dy; q.push(start); while(!q.empty()){ next=q.front(); q.pop(); for(int i=0;i<4;i++){ next.x=start.x+dir[i][0]; next.y=start.y+dir[i][1]; if(CHECK(next.y,next.y)&&room[next.x][next.y]=='.'){ room[next.x][next.y]='#'; num++; q.push(next); } } } } int main(){ int dx,dy,x,y; while(cin>>wx>>hy){ if(wx==0&&hy==0)break; for(y=0;y<hy;y++){ for(x=0;x<wx;x++){ cin>>room[x][y]; if(room[x][y]=='@'){ dx=x; dy=y; } } } num=0; BFS(dx,dy); cout<<num<<endl; } return 0; } ……

阅读全文

什么是归并排序 归并排序（Merge Sort）是利用归并的思想实现的排序方法，该算法采用经典的分治（divide-and-conquer）策略将问题分成一些小的问题然后递归求解，即分而治之。 图解 代码实现 #include<iostream>using namespace std; const int maxsize=5; typedef int datatype; typedef char othertype; typedef struct{ datatype key; othertype other; }rec; typedef rec list[maxsize+1]; list a; list b; void Inser(){ cout<<"请输入:"<<endl; for(int i=1;i<maxsize+1;i++){ cin>>a[i].other>>a[i].key; } } void Merge(list r,list r1,int low,int mid,int high){ int i,j,k; i=low; j=mid+1; k=low; while(i<=mid&&j<=high){ if(r[i].key<=r[j].key)r1[k++]=r[i++]; else r1[k++]=r[j++]; } while(i<=mid)r1[k++]=r[i++]; while(j<=high)r1[k++]=r[j++]; } void Merge_passage(list r,list r1,int n,int len){ int i=1; while(i+2*len-1<=n){ Merge(r,r1,i,i-1+len,i-1+2*len); } if(i-1+len<n){ Merge(r,r1,i,i-1+len,n); } else{ for(int j=i;j<n;j++){ r1[j]=r[j]; } } } void Merge_sort(list r,list r1,int n){ int len; len=1; while(len<n){ Merge_passage(r,r1,n,len);len=len*2; Merge_passage(r1,r,n,len);len=len*2; } } int main(){ Insert(); Merge_sort(a,b,maxsize); for (int i = 1; i < maxsize + 1; i++) { cout << b[i].……

阅读全文

本篇将讲述一下辗转相除法 GCD（欧几里得）算法求的是两数的最大公约数 LCM算法则是在GCD的基础上算出两数的最小公倍数 辗转相除法是利用以下性质来确定两个正整数 a 和 b 的最大公因子的： ⒈ 若 r 是 a ÷ b 的余数，且r不为0， 则 gcd(a,b) = gcd(b,r) ⒉ a 和其倍数之最大公因子为 a。 另一种写法是： ⒈ 令r为a/b所得余数（0≤r<b） 若 r= 0，算法结束；b 即为答案。 ⒉ 互换：置 a←b，b←r，并返回第一步。 代码如下: GCD给出了上述第二种互换的代码实现： inline int gcd(int a,int b) { return !b? a:gcd(b,a%b); } inline int lcm(int a,int b) { return a/gcd(a,b)*b; } ……

阅读全文