字符串匹配

主字符串s模式字符串t字符串匹配就是找出字符串t首次出现在s的下标位置1BF算法暴力算法概述根据平时的经验将模式字符串从头开始一个个与主字符串比对需要两层循环外层循环是控制主字符串要和模式字符串匹配时的起点内层循环便是每次都要将模式字符串从头开始遍历。这样的算法时间复杂度高2KMP算法时间复杂度低常用概述主要是求解模式字符串t的next根据模式字符串的next数组在匹配时进行移动。求解next的方法1下标从1开始默认next[1]0next[2]1;2从第3个元素开始计算next值。首先是看这个元素的前一个元素对应的next值找第next个元素(记作)是否和这个相等或者说一样如果相等则该元素对应的next是其前一个元素对应的next值1如果不相等则需要继续回溯找对应的next值找第next个元素的字符是否和一样如果一样那这个元素对应的next值等于此时找到的这个元素的所属位置就是在字符串中是第几个元素也可以说是这个元素的下标1的个数1如果还是没找到就继续回溯3但如果知道回溯到第一个元素也不相等的话我们就让这个元素的next0。匹配的方法1设置代表两个字符串的下标i,j分别设置为1不要搞混因为next的下标我们是从0开始的但字符串的下标是从0开始的这里设置1之后后续需要注意-12开始遍历两个字符串如果对应的字符相等下标分别向后移动继续对比3如果不等这时候需要借助我们的next。我们首先是需要保持我们主字符的下标i保持不动将模式字符的下标jnext[j]意思就是将下标j设置为此时字符对应的next值之后主字符从i,模式字符从新的对应下标为j的元素开始遍历对比遇到不一样的继续保持i不变jnext[j]需要注意如果遇到j0那么需要将i和j同时14当i或者j的大小超过我们所给对应的字符长度的时候遍历就结束了。结束之后我们可以对比j和模式字符串的长度如果j大于模式字符串的长度说明模式字符串已经被匹配上了那么返回(i-模式字符串的长度因为i此时的位置是与模式字符串匹配到尾对应的个数要返回匹配成功的第一个元素的下标。#include stdio.h #include string.h #include stdlib.h //被查找的字符串为模式串我们就是要查找模式串第一次出现在字符串的位置 //朴素匹配 int strMatch(char *str,char *pattern){ int nstrlen(str); int mstrlen(pattern); for(int i0;i(n-m);i){ int j0; while(jm){ if(str[i]pattern[j]){ i; j; }else{ ii-j; break; } } if(jm){ return i-j; } } return -1; } //KMP算法 //基于模式串确定next数组利用next数组完成字符串匹配在匹配过程中发生字符不匹配中next数组用俩帮助确定下一次的匹配位置 void get_next(char *s,int *next){ next[1]0; next[2]1; int nstrlen(s); int i3; int knext[i-1]; while(in){ if(s[k-1]s[i-1]){ next[i]next[i-1]1; knext[i]; i; }else{ knext[k]; if(k0){ next[i]1; knext[i]; i; } } } } int PiPei(char *s1,char *s2){ int *next(int *)malloc(sizeof(int)*strlen(s2)); get_next(s2,next); int index11,index21; int len1strlen(s1),len2strlen(s2); while(index1len1index2len2){ if(s1[index1-1]s2[index2-1]){ index1; index2; }else{ index2next[index2]; if(index20){ index1; index2; } } } if(index2len2){ return index1-len2-1; }else{ return -1; } } int main(){ char s1[]abcbbabc; char s2[]ba; strstr(s1,s2);//返回s2在s1第一次出现的位置 printf(\n); printf(%p\n,strstr(s1,s2));//对应输出的地址 for(int i0;i3;i){ printf(%p ,s1[i]); } //朴素匹配 int posstrMatch(s1,s2); printf(%d\n,pos); printf(%d\n,PiPei(s1,s2)); }