主字符串s模式字符串t字符串匹配就是找出字符串t首次出現(xiàn)在s的下標(biāo)位置1BF算法暴力算法概述根據(jù)平時(shí)的經(jīng)驗(yàn)將模式字符串從頭開(kāi)始一個(gè)個(gè)與主字符串比對(duì)需要兩層循環(huán)外層循環(huán)是控制主字符串要和模式字符串匹配時(shí)的起點(diǎn)內(nèi)層循環(huán)便是每次都要將模式字符串從頭開(kāi)始遍歷。這樣的算法時(shí)間復(fù)雜度高2KMP算法時(shí)間復(fù)雜度低常用概述主要是求解模式字符串t的next根據(jù)模式字符串的next數(shù)組在匹配時(shí)進(jìn)行移動(dòng)。求解next的方法1下標(biāo)從1開(kāi)始默認(rèn)next[1]0next[2]1;2從第3個(gè)元素開(kāi)始計(jì)算next值。首先是看這個(gè)元素的前一個(gè)元素對(duì)應(yīng)的next值找第next個(gè)元素(記作)是否和這個(gè)相等或者說(shuō)一樣如果相等則該元素對(duì)應(yīng)的next是其前一個(gè)元素對(duì)應(yīng)的next值1如果不相等則需要繼續(xù)回溯找對(duì)應(yīng)的next值找第next個(gè)元素的字符是否和一樣如果一樣那這個(gè)元素對(duì)應(yīng)的next值等于此時(shí)找到的這個(gè)元素的所屬位置就是在字符串中是第幾個(gè)元素也可以說(shuō)是這個(gè)元素的下標(biāo)1的個(gè)數(shù)1如果還是沒(méi)找到就繼續(xù)回溯3但如果知道回溯到第一個(gè)元素也不相等的話我們就讓這個(gè)元素的next0。匹配的方法1設(shè)置代表兩個(gè)字符串的下標(biāo)i,j分別設(shè)置為1不要搞混因?yàn)閚ext的下標(biāo)我們是從0開(kāi)始的但字符串的下標(biāo)是從0開(kāi)始的這里設(shè)置1之后后續(xù)需要注意-12開(kāi)始遍歷兩個(gè)字符串如果對(duì)應(yīng)的字符相等下標(biāo)分別向后移動(dòng)繼續(xù)對(duì)比3如果不等這時(shí)候需要借助我們的next。我們首先是需要保持我們主字符的下標(biāo)i保持不動(dòng)將模式字符的下標(biāo)jnext[j]意思就是將下標(biāo)j設(shè)置為此時(shí)字符對(duì)應(yīng)的next值之后主字符從i,模式字符從新的對(duì)應(yīng)下標(biāo)為j的元素開(kāi)始遍歷對(duì)比遇到不一樣的繼續(xù)保持i不變jnext[j]需要注意如果遇到j(luò)0那么需要將i和j同時(shí)14當(dāng)i或者j的大小超過(guò)我們所給對(duì)應(yīng)的字符長(zhǎng)度的時(shí)候遍歷就結(jié)束了。結(jié)束之后我們可以對(duì)比j和模式字符串的長(zhǎng)度如果j大于模式字符串的長(zhǎng)度說(shuō)明模式字符串已經(jīng)被匹配上了那么返回(i-模式字符串的長(zhǎng)度因?yàn)閕此時(shí)的位置是與模式字符串匹配到尾對(duì)應(yīng)的個(gè)數(shù)要返回匹配成功的第一個(gè)元素的下標(biāo)。#include stdio.h #include string.h #include stdlib.h //被查找的字符串為模式串我們就是要查找模式串第一次出現(xiàn)在字符串的位置 //樸素匹配 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數(shù)組利用next數(shù)組完成字符串匹配在匹配過(guò)程中發(fā)生字符不匹配中next數(shù)組用倆幫助確定下一次的匹配位置 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第一次出現(xiàn)的位置 printf(\n); printf(%p\n,strstr(s1,s2));//對(duì)應(yīng)輸出的地址 for(int i0;i3;i){ printf(%p ,s1[i]); } //樸素匹配 int posstrMatch(s1,s2); printf(%d\n,pos); printf(%d\n,PiPei(s1,s2)); }