添加网站备案号链接,哈尔滨建设局网站,注册公司流程和费用需要哪些条件,网站模板d一品资源网介绍两种字符串匹配方法1.暴力匹配母串用s表示#xff0c;长度为m子串用p表示#xff0c;长度为n时间复杂度为:(m-n1)n算法#xff1a;从s串的第一个字符开始匹配#xff0c;若匹配#xff0c;继续根据p向后匹配#xff0c;若后续的不匹配#xff0c;s右移重新匹配p 2.K…介绍两种字符串匹配方法1.暴力匹配母串用s表示长度为m子串用p表示长度为n时间复杂度为:(m-n1)n算法从s串的第一个字符开始匹配若匹配继续根据p向后匹配若后续的不匹配s右移重新匹配p 2.KMP算法母串用s表示长度为m子串用p表示长度为n时间复杂度为:预处理阶段m算法①计算next[]数组 ②字符串匹配【参考】 http://kb.cnblogs.com/page/176818/ http://www.cnblogs.com/gaochundong/p/string_matching.html http://blog.csdn.net/v_july_v/article/details/7041827 【C语言实现】 1.暴力匹配#include stdio.h#include string.hint main(){char *sASDFZGasdFZGdfasdFZGsdFZGFZG;char *pFZG;int i0,j0,count0;int len_sstrlen(s);int len_pstrlen(p);while(ilen_sjlen_p){if (s[i]p[j]){i;j;} else{ii-j1;j0;}if (len_pj){ printf(%d\n,i-j);//打印匹配成功的起始位置 count;//计算匹配次数 j0;}}printf(%d\n,count);//打印匹配次数return 0;} 2.KMP算法 #include stdio.h#include string.hint KmpSearch(char* s, char* p, int next[]);void GetNext(char* p,int next[]);int main(){char *sasfdafASDdfda;char *pSD;int next[3]{0};GetNext(p,next);KmpSearch(s,p,next);return 0;}int KmpSearch(char* s, char* p, int next[]) { int i 0; int j 0; int sLen strlen(s); int pLen strlen(p); while (i sLen j pLen) { //①如果j -1或者当前字符匹配成功即S[i] P[j]都令ij if (j -1 || s[i] p[j]) { i; j; } else { //②如果j ! -1且当前字符匹配失败即S[i] ! P[j]则令 i 不变j next[j] //next[j]即为j所对应的next值 j next[j]; } } if (j pLen){printf(%d\n,i-j);//打印匹配成功的起始位置 return i - j; }else return -1; } void GetNext(char* p,int next[]) //该函数为计算next[]数组看不太懂。。。算法暂且先记住吧{ int pLen strlen(p); next[0] -1; //第一位数字置为-1其余的是最长公共元素右移一位int k -1; int j 0; while (j pLen - 1) { //p[k]表示前缀p[j]表示后缀 if (k -1 || p[j] p[k]) { k; j; next[j] k; } else { k next[k]; } } } 转载于:https://www.cnblogs.com/kinghero/p/5604415.html
