http://hi.baidu.com/azuryy/blog/item/10d3d3460b97af0e6b63e5cd.html KMP算法详解 转帖 收藏 个人觉得这篇文章是网上的介绍有关KMP算法更让人容易理解的文章了，确实说得很“详细”，耐心地把它看完肯定会有所收获的～～，另外有关模式函数值next[i]确实有很多版本啊，在另外一些面向对象的算法描述
书
关于书的成语关于读书的排比句社区图书漂流公约怎么写关于读书的小报汉书pdf
中也有失效函数 f(j)的说法，其实是一个意思，即next[j]=f(j-1)+1，不过还是next[j]这种
表
关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf
示法好理解啊： KMP字符串模式匹配详解 KMP字符串模式匹配通俗点说就是一种在一个字符串中定位另一个串的高效算法。简单匹配算法的时间复杂度为O(m*n);KMP匹配算法。可以
证明
住所证明下载场所使用证明下载诊断证明下载住所证明下载爱问住所证明下载爱问
它的时间复杂度为O(m+n).。 一.简单匹配算法 先来看一个简单匹配算法的函数： int Index_BF ( char S [ ], char T [ ], int pos ) { /* 若串 S 中从第pos(S 的下标0≤pos
S[0] != S[1],S[1] != S[2],所以S[1] != T[0],S[2] != T[0]. 还是从理论上间接比较了。 有人疑问又来了，你分析的是不是特殊轻况啊。 假设S不变，在S中搜索T=“abaabd”呢？答：这种情况，当比较到S[2]和T[2]时，发现不等，就去看next[2]的值，next[2]=-1，意思是S[2]已经和T[0] 间接比较过了，不相等，接下来去比较S[3]和T[0]吧。 假设S不变，在S中搜索T=“abbabd”呢？答：这种情况当比较到S[2]和T[2]时，发现不等，就去看next[2]的值，next[2]=0，意思是S[2]已经和T[2]比较过了，不相等，接下来去比较S[2]和T[0]吧。 假设S=”abaabcabdabba”在S中搜索T=“abaabd”呢？答：这种情况当比较到S[5]和T[5]时，发现不等，就去看next[5]的值，next[5]=2，意思是前面的比较过了，其中，S[5]的前面有两个字符和T的开始两个相等，接下来去比较S[5]和T[2]吧。 总之，有了串的next值，一切搞定。那么，怎么求串的模式函数值next[n]呢？（本文中next值、模式函数值、模式值是一个意思。） 三. 怎么求串的模式值next[n] 定义： （1）next[0]= -1 意义：任何串的第一个字符的模式值规定为-1。 （2）next[j]= -1 意义：模式串T中下标为j的字符，如果与首字符 相同，且j的前面的1—k个字符与开头的1—k 个字符不等（或者相等但T[k]==T[j]）（1≤k
总结
初级经济法重点总结下载党员个人总结TXt高中句型全总结.doc高中句型全总结.doc理论力学知识点总结pdf
。 设在字符串S中查找模式串T，若S[m]!=T[n],那么，取T[n]的模式函数值next[n], 1. next[n]= -1 表示S[m]和T[0]间接比较过了，不相等，下一次比较 S[m+1] 和T[0] 2. next[n]=0 表示比较过程中产生了不相等，下一次比较 S[m] 和T[0]。 3. next[n]= k >0 但k #include int KMP(const char *Text,const char* Pattern) //const 表示函数内部不会改变这个参数的值。 { if( !Text||!Pattern|| Pattern[0]=='\0' || Text[0]=='\0' )// return -1;//空指针或空串，返回-1。 int len=0; const char * c=Pattern; while(*c++!='\0')//移动指针比移动下标快。 { ++len;//字符串长度。 } int *next=new int[len+1]; get_nextval(Pattern,next);//求Pattern的next函数值 int index=0,i=0,j=0; while(Text[i]!='\0' && Pattern[j]!='\0' ) { if(Text[i]== Pattern[j]) { ++i;// 继续比较后继字符 ++j; } else { index += j-next[j]; if(next[j]!=-1) j=next[j];// 模式串向右移动 else { j=0; ++i; } } }//while delete []next; if(Pattern[j]=='\0') return index;// 匹配成功 else return -1; } int main()//abCabCad { char* text="bababCabCadcaabcaababcbaaaabaaacababcaabc"; char*pattern="adCadCad"; //getNext(pattern,n); //get_nextval(pattern,n); cout<
设计
领导形象设计圆作业设计ao工艺污水处理厂设计附属工程施工组织设计清扫机器人结构设计
一个文本编辑器的实际问题的过程中创建了差不多是同样的算法。这里可以看到并不是所有的算法都是“灵光一现”中被发现的，而理论化的计算机科学确实在一些时候会应用到实际的应用中。 BM http://heikediguo2005.blog.163.com/blog/static/221197120100893710429/ http://wenku.baidu.com/view/dde42b08763231126edb112f.html http://forum.byr.edu.cn/pc/pccon.php?id=1117&nid=51194 http://kmplayer.javaeye.com/blog/704125 http://forum.byr.edu.cn/pc/pccon.php?id=1117&nid=51194 http://blog.csdn.net/qqj_1228/archive/2010/01/17/5204779.aspx http://zhidao.baidu.com/question/120565201.html http://www.javaeye.com/wiki/topic/704187 附程序： #include #include int getNext(const char* num, int next[]) { int j, k; j = 0; k = -1; next[0] = -1; while(num[j] != '\0') { if(k == -1 || num[j] == num[k]) { ++ j; ++ k; if(num[j] != num[k]) next[j] = k; else next[j] = next[k]; } else { k = next[k]; } } return 0; } int KMP(const char* s, const char* t, const int* next) { int i, j; i = 0; j = 0; while(s[i] != '\0' && t[j] != '\0') { if(s[i] == t[j]) { ++ i; ++ j; } else { if(next[j] == -1) { j = 0; ++ i; } else { j = next[j]; } } } if(t[j] == '\0') return i - strlen(t); else return -1; } int main() { char s[] = "acabaabaabcacaabc"; char t[] = "abaabc"; int next[10]; getNext(t, next); for(int i = 0; i < strlen(t); i ++) printf("%d ", next[i]); printf("\n"); printf("%d", KMP(s, t, next)); while(1); return 0; }
浙公网安备 33021202002483