chinese直男口爆体育生外卖, 99久久er热在这里只有精品99, 又色又爽又黄18禁美女裸身无遮挡, gogogo高清免费观看日本电视,私密按摩师高清版在线,人妻视频毛茸茸,91论坛 兴趣闲谈,欧美 亚洲 精品 8区,国产精品久久久久精品免费

0
  • 聊天消息
  • 系統(tǒng)消息
  • 評(píng)論與回復(fù)
登錄后你可以
  • 下載海量資料
  • 學(xué)習(xí)在線課程
  • 觀看技術(shù)視頻
  • 寫(xiě)文章/發(fā)帖/加入社區(qū)
會(huì)員中心
創(chuàng)作中心

完善資料讓更多小伙伴認(rèn)識(shí)你,還能領(lǐng)取20積分哦,立即完善>

3天內(nèi)不再提示

關(guān)于字符串硬核講解

FPGA之家 ? 來(lái)源:FPGA之家 ? 作者:FPGA之家 ? 2022-06-26 10:42 ? 次閱讀
加入交流群
微信小助手二維碼

掃碼添加小助手

加入工程師交流群

1 暴力破解法

在主串A中查找模式串B的出現(xiàn)位置,其中如果A的長(zhǎng)度是n,B的長(zhǎng)度是m,則n > m。當(dāng)我們暴力匹配時(shí),在主串A中匹配起始位置分別是 0、1、2….n-m 且長(zhǎng)度為 m 的 n-m+1 個(gè)子串。

db273a1e-f4e9-11ec-ba43-dac502259ad0.png暴力匹配
對(duì)應(yīng)代碼是:
#include
#include
intcnt=0;
intindex(chars[],charsub[])
{
inti=0;
intj=0;
while(i<strlen(s))
{
if(s[i]==sub[j])
{//單個(gè)字符相等的話i和j都向后搜索
i++;
j++;
}
else
{//有字符不匹配的話,i從上一次的下一個(gè)位置開(kāi)始,模式串j再?gòu)?開(kāi)始
i=i-j+1;
j=0;
}
if(j==strlen(sub))
{
cnt++;
returni-strlen(sub)+1;
}
}
return-1;
}
intmain()
{
// s="abcdabefgabefa",sub="abe",返回 5。
chars[20],sub[10];
gets(s);
gets(sub);
printf("%d
",cnt);
printf("%d
",index(s,sub));
return0;
}

如果主串是bbb…bbb,模式串是bbbbc,那每個(gè)串都要比較m次,一共是(n-m+1)*m次。時(shí)間復(fù)雜度很大 = O(n*m),一般簡(jiǎn)單匹配時(shí)候可用此法。

2 Rabin-Karp 算法

算法思路:對(duì)主串的 n-m+1 個(gè)子串分別求哈希值,然后跟模板串的哈希值對(duì)比,如果一樣再逐個(gè)對(duì)比字符串是否一樣。

db39bb3a-f4e9-11ec-ba43-dac502259ad0.pngRabin-Karp算法
但是中間數(shù)據(jù)的Hash值計(jì)算是可以優(yōu)化的,我們以簡(jiǎn)單的字符串匹配舉例,把a(bǔ)-z映射到0~25上。然后按照26進(jìn)制計(jì)算一個(gè)串的哈希值,比如:
db46d590-f4e9-11ec-ba43-dac502259ad0.pngHash計(jì)算
但是你會(huì)發(fā)現(xiàn)相鄰的兩個(gè)子串?dāng)?shù)據(jù)之間是有重疊的,比如dababc重疊了ab。這樣哈希下一個(gè)數(shù)據(jù)的Hash值其實(shí)可以借鑒下上一個(gè)數(shù)據(jù)的值推導(dǎo)得出:
db57640a-f4e9-11ec-ba43-dac502259ad0.png優(yōu)化計(jì)算哈希值
RK算法的時(shí)間復(fù)雜度包含兩部分,第一部分是遍歷所有子串計(jì)算Hash值,時(shí)間復(fù)雜度是O(n)。第二部分是比較哈希值,這部分時(shí)間復(fù)雜度也是O(n)。

這個(gè)算法的核心就是盡量減少哈希值相等的情況下數(shù)據(jù)不一樣從而進(jìn)行的比較,所以哈希算法要盡可能的好,如果你感覺(jué)用123對(duì)應(yīng)字母abc容易碰撞,那用素?cái)?shù)去匹配也是OK的,反正目的是一樣的, 你可以認(rèn)為這是一種取巧的辦法來(lái)處理字符串匹配問(wèn)題。

3 Boyer-Moore 算法。

Boyer Moore算法是一種非常高效的字符串匹配算法,它的性能是著名的 KMP 算法的 3 到 4 倍。它不太好理解,但確是工程中使用最多的字符串匹配算法。以前我們匹配字符串的時(shí)候是一個(gè)個(gè)從前往后挪動(dòng)來(lái)逐次比較,BM 算法核心思想是在模式串中某個(gè)字符與主串不能匹配時(shí),將模式串往后多滑動(dòng)幾位,來(lái)減少不必要的字符比較。

db631f7a-f4e9-11ec-ba43-dac502259ad0.png移動(dòng)比較對(duì)比
整體而言BM算法還是挺復(fù)雜的相比前面兩種,主要包含壞字符規(guī)則好后綴規(guī)則。

3.1 壞字符規(guī)則

壞字符規(guī)則意思是根據(jù)模式串從后往前匹配,當(dāng)我們發(fā)現(xiàn)某個(gè)字符沒(méi)法匹配的時(shí)候。我們把這個(gè)沒(méi)有匹配的主串中的字符叫作壞字符

db6dcf10-f4e9-11ec-ba43-dac502259ad0.png壞字符
找到壞字符c后,在模式串中繼續(xù)查找發(fā)現(xiàn)c跟模式串任何字符無(wú)法匹配,則可以直接將模式串往后移動(dòng)3位。繼續(xù)從模式串尾部對(duì)比。
db77731c-f4e9-11ec-ba43-dac502259ad0.png移動(dòng)2格
此時(shí)發(fā)現(xiàn)壞字符是g,但在模式串中有個(gè)g存在,不能再往后移動(dòng)3個(gè)了,移動(dòng)的位置是2個(gè)。再繼續(xù)匹配。那有啥規(guī)律呢?

發(fā)送不匹配時(shí),壞字符對(duì)應(yīng)的模式串字符下標(biāo)位置Si,如果壞字符在模式串中存在,取從后往前最先出現(xiàn)的壞字符下標(biāo)記為Xi(取第一個(gè)是怕挪動(dòng)太大咯),如果壞字符在模式串中不存在則Xi = -1。此時(shí)模式串往后移動(dòng)位數(shù)= Si - Xi

db88aa4c-f4e9-11ec-ba43-dac502259ad0.png壞字符移動(dòng)規(guī)則
如果碰到極致的主串=cccdcccdcccd,模式串=cccc,那此時(shí)時(shí)間復(fù)雜度是O(n/m)。
db9c903e-f4e9-11ec-ba43-dac502259ad0.png最優(yōu)解
但是不要高興太早!下面這種情況可能導(dǎo)致模式串不往后移動(dòng),反而往前移動(dòng)哦!
dbb73bc8-f4e9-11ec-ba43-dac502259ad0.png往前移動(dòng)?
所以此時(shí)BM算法還需要用到好后綴規(guī)則

3.2 壞字符代碼

為避免每次都拿懷字符從模式串中遍歷查找,此時(shí)用到散列表將模式串中每個(gè)字符及其下標(biāo)存起來(lái),方便迅速查找。

接下來(lái)說(shuō)下散列表規(guī)則,比如一個(gè)字符是一個(gè)字節(jié),用大小為256的數(shù)組記錄每個(gè)字符在模式串出現(xiàn)位置,數(shù)組中存儲(chǔ)的是模式串出現(xiàn)的位置,數(shù)組下表是字符對(duì)應(yīng)的ASCII值。

dbc14226-f4e9-11ec-ba43-dac502259ad0.png哈希規(guī)則 壞字符規(guī)則:
//全局變量 SIZE
privatestaticfinalintSIZE=256;
//b=模式串?dāng)?shù)組,m是模式串?dāng)?shù)組長(zhǎng)度,sl是哈希表,默認(rèn)-1
privatevoidgenerateBC(char[]b,intm,int[]sl){
for(inti=0;i-1;//初始化sl
}
for(inti=0;iintascii=(int)b[i];
sl[ascii]=i;
}
}

接下來(lái)先不考慮好后綴規(guī)則跟壞字符的負(fù)數(shù)情況,先大致寫(xiě)出 BM 算法代碼。

dbd90ad2-f4e9-11ec-ba43-dac502259ad0.png壞字符BM
publicintbm(char[]a,intn,char[]b,intm){
//記錄模式串中每個(gè)字符最后出現(xiàn)的位置
int[]sl=newint[SIZE];
//構(gòu)建壞字符哈希表
generateBC(b,m,sl);
//i表示主串與模式串對(duì)齊的第一個(gè)字符
inti=0;
while(i<=?n?-?m)?{
????intj;
for(j=m-1;j>=0;j--){
if(a[i+j]!=b[j])break;
}
if(j0){
//匹配成功,返回主串與模式串第一個(gè)匹配的字符的位置
returni;
}
//將模式串往后滑動(dòng)j-bc[(int)a[i+j]]位
i=i+(j-sl[(int)a[i+j]]);
}
return-1;
}

3.3 好后綴規(guī)則

好后綴跟壞后綴道理類似,從后往前匹配,直到遇到不匹配的字符x,那主串x之前的就叫好后綴。

dbe9e0e6-f4e9-11ec-ba43-dac502259ad0.png好后綴定義
此時(shí)移動(dòng)的規(guī)則如下:
  1. 如果好后綴在模式串中找到了,用x框起來(lái),然后將x框跟好后綴對(duì)齊繼續(xù)匹配。

    dbf9aeae-f4e9-11ec-ba43-dac502259ad0.png找到了移動(dòng)規(guī)則
  2. 找不到的時(shí)候,如果直接移動(dòng)長(zhǎng)度是模式串m位,那極有可能過(guò)度了!而過(guò)度移動(dòng)存在的原因就是,比如你找了好后綴u,u在模式串中整體沒(méi)找到,但是u的子串d是可以跟模式串匹配上的啊。

    dc0d6386-f4e9-11ec-ba43-dac502259ad0.png過(guò)度移動(dòng)

所以此時(shí)還要看好后綴的后綴子串是否跟模式串中的前綴子串匹配,從好后綴串的后后綴子串中找個(gè)最長(zhǎng)能跟模式串的前綴子串匹配的然后滑動(dòng)到一起,比如上面的d。

然后分別計(jì)算壞字符往后滑動(dòng)位數(shù)跟好后綴往后滑動(dòng)此時(shí),兩者取其大作為模式串往后滑動(dòng)位數(shù),這種情況下還可以避免壞字符的負(fù)數(shù)情況。

3.4 好后綴代碼

好后綴的核心其實(shí)就在于兩點(diǎn)

  1. 在模式串中,查找跟好后綴匹配的另一個(gè)子串。

  2. 在好后綴的后綴子串中,查找最長(zhǎng)的、能跟模式串前綴子串匹配的后綴子串。

3.4.1 預(yù)處理工作

上面兩個(gè)核心點(diǎn)可以在代碼層面用暴力解決,但太耗時(shí)!我們可以在匹配前通過(guò)預(yù)處理模式串,預(yù)先計(jì)算好模式串的每個(gè)后綴子串,對(duì)應(yīng)的另一個(gè)可匹配子串的位置。

先看如何表示模式串中不同的后綴子串,因?yàn)楹缶Y子串的最后個(gè)字符下標(biāo)為m-1,我們只需記錄后綴子串長(zhǎng)度即可,通過(guò)長(zhǎng)度可以確定一個(gè)唯一的后綴子串。

dc202c50-f4e9-11ec-ba43-dac502259ad0.png子串表示
再引入關(guān)鍵的變量suffix數(shù)組。suffix 數(shù)組的index表示后綴子串的長(zhǎng)度。下標(biāo)對(duì)應(yīng)的數(shù)組值存儲(chǔ)的是
好后綴在模式串中匹配的起始下標(biāo)值:
dc2e78f0-f4e9-11ec-ba43-dac502259ad0.pngsuffix數(shù)組定義
比如此處后綴子串c在模式串中另一個(gè)匹配開(kāi)始位置為2, 后綴子串bc在模式串中另一個(gè)匹配開(kāi)始位置為1 后綴子串dbc在模式串中另一個(gè)匹配開(kāi)始位置為0, 后綴子串cdbc在模式串中只出現(xiàn)了一次,所以為-1。
dc404bf2-f4e9-11ec-ba43-dac502259ad0.pngprefix 數(shù)組
這里需注意,我們不僅要在模式串中查找跟好后綴匹配的另一個(gè)子串,還要在好后綴的后綴子串中查找最長(zhǎng)的能跟模式串前綴子串匹配的后綴子串。比如下面:
dc5200a4-f4e9-11ec-ba43-dac502259ad0.png最長(zhǎng)模式匹配

suffix只能查找跟好后綴匹配的另一個(gè)子串。但還需要個(gè) boolean 類型的prefix數(shù)組來(lái)記錄模式串的后綴子串是否能匹配模式串的前綴子串。

接下來(lái)重點(diǎn)看下如何填充suffixprefix數(shù)組,拿下標(biāo)從 0 到 i 的子串與整個(gè)模式串,求公共后綴子串,其中i=[0,m-2]。如果公共后綴子串的長(zhǎng)度是 k,就suffix[k]=j,其中 j 表示公共后綴子串的起始下標(biāo)。如果 j = 0,說(shuō)明公共后綴子串也是模式串的前綴子串,此時(shí) prefix[k]=true。

dc615478-f4e9-11ec-ba43-dac502259ad0.pngsuffix跟prefix數(shù)組
//b=模式串,m=模式串長(zhǎng)度,suffix,prefix數(shù)組如上定義
privatevoidgenerateGS(char[]b,intm,int[]suffix,boolean[]prefix){
//初始化
for(inti=0;ii++){
suffix[i]=-1;
prefix[i]=false;
}
//b[0,i]
for(inti=0;i1;i++){
intj=i;
//公共后綴子串長(zhǎng)度
intk=0;
//與b[0, m-1]求公共后綴子串,并且會(huì)有覆蓋現(xiàn)象產(chǎn)生。
while(j>=0&&b[j]==b[m-1-k]){
--j;
++k;
//j+1表示公共后綴子串在b[0,i]中的起始下標(biāo)
suffix[k]=j+1;
}
//如果公共后綴子串也是模式串的前綴子串
if(j==-1)prefix[k]=true;
}
}
3.4.2 正式代碼

有了suffixprefix數(shù)組后,看下移動(dòng)規(guī)則。假設(shè)好后綴串長(zhǎng)度=k,如果k != 0,說(shuō)明有好后綴,接下來(lái)通過(guò)suffix[k]的值來(lái)判斷如何移動(dòng)。

  1. suffix[k] != -1,不等于時(shí)說(shuō)明匹配上了,模式串后移 j-suffix[k]+1 位,其中 j 表示壞字符對(duì)應(yīng)的模式串中的字符下標(biāo)。

  2. suffix[k] = -1,等于時(shí)說(shuō)明好后綴沒(méi)匹配上,那就看下子串的匹配情況,好后綴的后綴子串長(zhǎng)度是 b[r, m-1],其中 r = [j+2,m-1],后綴子串長(zhǎng)度 k=m-r,如果 prefix[k] = true,說(shuō)明長(zhǎng)度為 k 的后綴子串有可匹配的前綴子串,這樣我們可以把模式串后移 r 位。

  3. 如果都沒(méi)匹配上,那就直接將模式串后移m位。

    // a跟n 分別表示主串跟主串長(zhǎng)度。
    // b跟m 分別表示模式串跟模式串長(zhǎng)度。
    publicintbm(char[]a,intn,char[]b,intm){
    //用來(lái)記錄模式串中每個(gè)字符最后出現(xiàn)的位置
    int[]sl=newint[SIZE];
    //構(gòu)建壞字符哈希表
    generateBC(b,m,sl);
    int[]suffix=newint[m];
    boolean[]prefix=newboolean[m];
    //構(gòu)建suffix跟prefix數(shù)組
    generateGS(b,m,suffix,prefix);
    inti=0;//j表示主串與模式串匹配的第一個(gè)字符
    while(i<=?n?-?m)?{
    ????intj;
    //模式串從后往前匹配
    for(j=m-1;j>=0;--j){
    //壞字符對(duì)應(yīng)模式串中的下標(biāo)是j
    if(a[i+j]!=b[j])break;
    }
    if(j0){
    //匹配OK,返回主串與模式串第一個(gè)匹配的字符的位置
    returni;
    }
    //壞字符計(jì)算所得需移動(dòng)長(zhǎng)度
    intx=j-sl[(int)a[i+j]];
    inty=0;
    //j
    if(j-1){
    y=moveByGS(j,m,suffix,prefix);
    }
    i=i+Math.max(x,y);
    }
    return-1;
    }
    
    //j=壞字符對(duì)應(yīng)的模式串中的字符下標(biāo)
    //m=模式串長(zhǎng)度
    privateintmoveByGS(intj,intm,int[]suffix,boolean[]prefix){
    //好后綴長(zhǎng)度
    intk=m-1-j;
    if(suffix[k]!=-1){
    //好后綴可以匹配上,返回需移動(dòng)長(zhǎng)度
    returnj-suffix[k]+1;
    }
    //有匹配到好后綴子串的模式串前綴子串
    for(intr=j+2;r<=?m-1;++r){
    if(prefix[m-r]==true){
    returnr;
    }
    }
    //沒(méi)找到直接移動(dòng)最大值
    returnm;
    }
    

3.5 復(fù)雜度分析

整個(gè)BM算法用到了額外的 sl、suffix、prefix三個(gè)數(shù)組,其中sl數(shù)組大小跟字符集大小有關(guān),suffix 數(shù)組和 prefix 數(shù)組的大小跟模式串長(zhǎng)度 m 有關(guān)。如果處理字符集很大的字符串匹配問(wèn)題,bc 數(shù)組對(duì)內(nèi)存的消耗就會(huì)比較多。

因?yàn)楹煤缶Y和壞字符規(guī)則是獨(dú)立的,如果我們運(yùn)行的環(huán)境對(duì)內(nèi)存要求苛刻,可以只使用好后綴規(guī)則,不使用壞字符規(guī)則,這樣就可以避免 bc 數(shù)組過(guò)多的內(nèi)存消耗。不過(guò),單純使用好后綴規(guī)則的 BM 算法效率就會(huì)下降一些了。

BM 算法的時(shí)間復(fù)雜度分析起來(lái)是非常復(fù)雜,一般在3n~5n之間。

4 KMP 算法

KMP算法跟BM算法類似,從前往后匹配,把能匹配上的叫好前綴,不能匹配上的叫壞字符。

dc6aee3e-f4e9-11ec-ba43-dac502259ad0.pngKMP匹配定義
遇到壞字符后就要進(jìn)行主串好前綴后綴子串跟模式串的前綴子串進(jìn)行對(duì)比,問(wèn)題是對(duì)于已經(jīng)比對(duì)過(guò)的好前綴,能否找到一種規(guī)律,將模式串一次性滑動(dòng)很多位?
dc7b45d6-f4e9-11ec-ba43-dac502259ad0.png暴力破解

思路是將主串中好前綴的后綴子串和模式串中好前綴的前綴子串進(jìn)行對(duì)比,獲取模式串中最大可以匹配的前綴子串。一般把好前綴的所有后綴子串中,最長(zhǎng)的可匹配前綴子串的那個(gè)后綴子串,叫作最長(zhǎng)可匹配后綴子串。對(duì)應(yīng)的前綴子串,叫作最長(zhǎng)可匹配前綴子串。假如現(xiàn)在最長(zhǎng)可匹配后綴子串 = u,最長(zhǎng)可匹配前綴子串 = v,獲得uv的長(zhǎng)度為k,此時(shí)在主串中壞字符位置為i,模式串中為j,接下來(lái)將模式串后移j-k位,然后將待比較的模式串位置j = j-k進(jìn)行比較。

dc86fca0-f4e9-11ec-ba43-dac502259ad0.pngKMP算法移動(dòng)

4.1 Next 數(shù)組存在意義

那最長(zhǎng)可匹配前綴跟后綴我們用模式串就可以求解了。仿照BM算法,預(yù)先計(jì)算好就行。在KMP算法中提前構(gòu)造個(gè)next數(shù)組。其中next數(shù)組的下標(biāo)用來(lái)存儲(chǔ)前綴子串最后一個(gè)數(shù)據(jù)的index,對(duì)應(yīng)的value保存的是這個(gè)字符串的后綴子串集合跟前綴子串集合的交集。

干說(shuō)可能不太好理解,我們以"abababca"為例。它的部分匹配表(Partial Match Table)數(shù)組如下:

dc92760c-f4e9-11ec-ba43-dac502259ad0.pngNext數(shù)組
接下來(lái)對(duì)value值的獲取進(jìn)行解釋,如果字符串A和B,存在A=BS,其中S是任意的非空字符串,那就稱B為A的前綴。例如”what”的前綴包括{"w","wh","wha"},我們把所有前綴組成的字符串的前綴集合。同樣可以定義后綴A=SB, 其中S是任意的非空字符串,那就稱B為A的后綴,例如"Potter"的后綴包括{"otter", "tter", "ter", "er", "r"},然后把所有后綴組成字符串的后綴集合。要注意字符串本身并不是自己的后綴

PMT數(shù)組中的值是字符串的前綴集合與后綴集合的交集中最長(zhǎng)元素的長(zhǎng)度。例如,對(duì)于"aba",它的前綴集合為{"a", "ab"},后綴集合為{"ba", "a"}。兩個(gè)集合的交集為{"a"},那么長(zhǎng)度最長(zhǎng)的元素就是字符串"a"了,長(zhǎng)度為1,所以"aba"的Next數(shù)組value = 1,同理對(duì)于"ababa",它的前綴集合為{"a", "ab", "aba", "abab"},它的后綴集合為{"baba", "aba", "ba", "a"}, 兩個(gè)集合的交集為{"a", "aba"},其中最長(zhǎng)的元素為"aba",長(zhǎng)度為3。

我們以主串"ababababca"中查找模式串"abababca"為例,如果在j處字符不匹配了,那在模式串[0,j-1]的數(shù)據(jù)串"ababab"中,前綴集合跟后綴集合的交集最大值就是長(zhǎng)度為4的"abab"。

dc9b1582-f4e9-11ec-ba43-dac502259ad0.pngPMT數(shù)組使用方法
基于此就可以使用PMT加速字符串的查找了。我們看到如果是在j位失配,那么影響j 指針回溯的位置的其實(shí)是第 j?1 位的 PMT 值,但是編程中為了方便一般不直接使用PMT數(shù)組而是使用Next數(shù)組,Next數(shù)組的value其實(shí)就是存儲(chǔ)的這個(gè)前綴的最長(zhǎng)可以匹配前綴子串的結(jié)尾字符下標(biāo),其中如果匹配不到用-1代替。
dca6e6aa-f4e9-11ec-ba43-dac502259ad0.pngNext數(shù)組使用

4.2 KMP 匹配代碼

// a =主串,n=主串長(zhǎng)度。b =模式串,m =模式串長(zhǎng)度
publicstaticintkmp(char[]a,intn,char[]b,intm){
int[]next=getNexts(b,m);
intj=0;
for(inti=0;iwhile(j>0&&a[i]!=b[j]){
j=next[j-1]+1;//發(fā)現(xiàn)不一樣則保持i不變j進(jìn)行移動(dòng)
}
if(a[i]==b[j]){
++j;
}
if(j==m){//找到匹配模式串的了
returni-m+1;
}
}
return-1;
}

至此你會(huì)發(fā)現(xiàn)只要搞明白了PMT存在的意義,然后順著思路推Next數(shù)組即可。

4.3 Next 數(shù)組求解

當(dāng)要計(jì)算next[i]時(shí),前面計(jì)算過(guò)的next[0~i-1]是否可以被用來(lái)快速推導(dǎo)出next[i]呢?

情況一:如果next[i-1] = k-1,那此時(shí)b[0,i-1]的最長(zhǎng)可匹配前綴子串是b[0,k-1],如果b[0,i-1]的下個(gè)字符b[i]跟b[0,k-1]的下個(gè)字符b[k]相等,那next[i] = k。

dcb9405c-f4e9-11ec-ba43-dac502259ad0.png
情況二:假設(shè)b[0,i]最長(zhǎng)可用后綴子串是b[r,i],那b[r,i-1]肯定是b[0,i-1]的可匹配后綴子串,但不一定是最長(zhǎng)可匹配后綴子串。比如字符串b = "dexdecdexdex",此時(shí)最長(zhǎng)可匹配后綴子串是"dex",b去掉最后的'x'成為B,此時(shí)雖然"de"是B的可匹配后綴子串,但"dexde"才是最長(zhǎng)后綴子串!也就是說(shuō)b[0, i-1]最長(zhǎng)可匹配后綴子串對(duì)應(yīng)的模式串的前綴子串的下一個(gè)字符并不等于 b[i]。
dcc496e6-f4e9-11ec-ba43-dac502259ad0.png
那此時(shí)看下b[0,i-1]的次長(zhǎng)可匹配后綴子串b[x,i-1]對(duì)應(yīng)的可匹配前綴子串b[0,i-1-x] 的下個(gè)字符b[i-x] 是否等于b[i],相等那b[0,i]的最長(zhǎng)可匹配后綴子串是b[x,i]。
dcd1be84-f4e9-11ec-ba43-dac502259ad0.png

那我們來(lái)求 b[0, i-1]的次長(zhǎng)可匹配后綴子串呢?次長(zhǎng)可匹配后綴子串一定被包含在最長(zhǎng)可匹配后綴子串中,而最長(zhǎng)可匹配后綴子串又對(duì)應(yīng)最長(zhǎng)可匹配前綴子串 b[0, y]。此時(shí)查找 b[0, i-1]的次長(zhǎng)可匹配后綴子串變成了查找b[0, y]的最長(zhǎng)匹配后綴子串的問(wèn)題。

按此思路考察完所有的 b[0, i-1]的可匹配后綴子串 b[y, i-1],直到找到一個(gè)可匹配的后綴子串,它對(duì)應(yīng)的前綴子串的下一個(gè)字符等于 b[i],那這個(gè) b[y, i]就是 b[0, i]的最長(zhǎng)可匹配后綴子串。

dcdf81d6-f4e9-11ec-ba43-dac502259ad0.png
//b=模式串,m=模式串的長(zhǎng)度
privatestaticint[]getNexts(char[]b,intm){
int[]next=newint[m];
next[0]=-1;
intk=-1;
for(inti=1;iwhile(k!=-1&&b[k+1]!=b[i]){
k=next[k];
//因?yàn)榍耙粋€(gè)的最長(zhǎng)串的下一個(gè)字符不與最后一個(gè)相等,需要找前一個(gè)的次長(zhǎng)串,
//問(wèn)題就變成了求0到next(k)的最長(zhǎng)串,如果下個(gè)字符與最后一個(gè)不等,
//繼續(xù)求次長(zhǎng)串,也就是下一個(gè)next(k),直到找到,或者完全沒(méi)有
//最好結(jié)合前面的圖來(lái)看
}
if(b[k+1]==b[i]){
++k;//字符串相等則看下一個(gè)
}
next[i]=k;//數(shù)組賦值
}
returnnext;
}

KMP空間復(fù)雜度:該算法只需要一個(gè)額外的 next 數(shù)組,數(shù)組的大小跟模式串相同。所以空間復(fù)雜度是 O(m),m 表示模式串的長(zhǎng)度。
KMP時(shí)間復(fù)雜度:next 數(shù)組計(jì)算的時(shí)間復(fù)雜度是 O(m) + 匹配時(shí)候時(shí)間復(fù)雜度是 O(n) = O(m+n)

至此,常見(jiàn)的字符串匹配算法正式講解完畢,其實(shí)前面說(shuō)的都是一個(gè)主串,一個(gè)模式串。

審核編輯 :李倩


聲明:本文內(nèi)容及配圖由入駐作者撰寫(xiě)或者入駐合作網(wǎng)站授權(quán)轉(zhuǎn)載。文章觀點(diǎn)僅代表作者本人,不代表電子發(fā)燒友網(wǎng)立場(chǎng)。文章及其配圖僅供工程師學(xué)習(xí)之用,如有內(nèi)容侵權(quán)或者其他違規(guī)問(wèn)題,請(qǐng)聯(lián)系本站處理。 舉報(bào)投訴
  • 字符串
    +關(guān)注

    關(guān)注

    1

    文章

    596

    瀏覽量

    23129

原文標(biāo)題:字符串硬核講解

文章出處:【微信號(hào):zhuyandz,微信公眾號(hào):FPGA之家】歡迎添加關(guān)注!文章轉(zhuǎn)載請(qǐng)注明出處。

收藏 人收藏
加入交流群
微信小助手二維碼

掃碼添加小助手

加入工程師交流群

    評(píng)論

    相關(guān)推薦
    熱點(diǎn)推薦

    字符串控件與靜態(tài)字符串控件中預(yù)覽字符顯示亂碼,如何修改顯示正常?

    字符串控件與靜態(tài)字符串控件中預(yù)覽字符顯示亂碼,如何修改顯示正常?
    發(fā)表于 01-20 17:17

    字符串,數(shù)字控件如何控制背景顏色和前景字體顏色?

    字符串,數(shù)字控件如何控制背景顏色和前景字體顏色?
    發(fā)表于 01-20 15:12

    Linux下怎么讓中文字符串按照拼音排序?

    求教 Linux 下怎么讓中文字符串按照拼音排序?
    發(fā)表于 01-06 07:40

    字符串關(guān)聯(lián)數(shù)字變量如何使用?我們的地址都是16位數(shù)據(jù),可以使用16位數(shù)字變量顯示字符串嗎?

    字符串關(guān)聯(lián)數(shù)字變量如何使用?我們的地址都是16位數(shù)據(jù),可以使用16位數(shù)字變量顯示字符串嗎?
    發(fā)表于 12-15 08:24

    飛凌嵌入式ElfBoard-標(biāo)準(zhǔn)IO接口之格式化輸出

    ( const char *format, ... );3)參數(shù)format:表示C 字符串,包含了要打印的格式化數(shù)據(jù)。...:表示附加可變參數(shù),根據(jù)不同的 format 字符串,函數(shù)可能需要一系列的附加
    發(fā)表于 11-11 08:43

    求助,關(guān)于cubemx + nano 4.1.1 + STM32F405時(shí)鐘的問(wèn)題求解

    NANO 4.1.1版本的MDK工程,mian里代碼寫(xiě)的是一秒打印一次字符串,但是出現(xiàn)的效果了,一秒鐘一次性打印了10次字符串 看起來(lái)似乎是有關(guān)時(shí)鐘配置的問(wèn)題,因?yàn)橐幻腌妱偤么蛴∈?b class='flag-5'>字符串,然后我嘗試
    發(fā)表于 09-16 06:05

    如何使用 NuMaker 板和 Mbed OS 上的連接字符串連接到 Azure IoT?

    使用 NuMaker 板和 Mbed OS 上的連接字符串連接到 Azure IoT
    發(fā)表于 09-04 07:46

    非對(duì)稱密鑰生成和轉(zhuǎn)換規(guī)格詳解

    當(dāng)前章節(jié)將說(shuō)明系統(tǒng)目前支持的算法及其對(duì)應(yīng)的規(guī)格。密鑰生成有兩種指定規(guī)格的方式,分別是: 字符串參數(shù):以字符串的形式描述開(kāi)發(fā)者需要生成的密鑰規(guī)格。 密鑰參數(shù):使用密鑰的詳細(xì)密碼學(xué)信息,構(gòu)造密鑰對(duì)象
    發(fā)表于 09-01 07:50

    LM3466 多 LED 電流平衡器技術(shù)手冊(cè)

    到電源的數(shù)或每個(gè) LED 的正向電壓 字符串。 如果任何 LED 燈在運(yùn)行過(guò)程中打開(kāi),LM3466 會(huì)自動(dòng)平衡通過(guò)所有剩余活動(dòng) LED 燈的電源電流。 如 因此,即使一些 LED
    的頭像 發(fā)表于 08-29 14:27 ?976次閱讀
    LM3466 多<b class='flag-5'>串</b> LED 電流平衡器技術(shù)手冊(cè)

    labview如何生成一個(gè)帶字符串返回的dll

    labview如何生成一個(gè)dll,如下圖,要求一個(gè)輸入,類型是字符串,返回類型也是字符串
    發(fā)表于 08-28 23:20

    在Python中字符串逆序有幾種方式,代碼是什么

    對(duì)于一個(gè)給定的字符串,逆序輸出,這個(gè)任務(wù)對(duì)于python來(lái)說(shuō)是一種很簡(jiǎn)單的操作,畢竟強(qiáng)大的列表和字符串處理的一些列函數(shù)足以應(yīng)付這些問(wèn)題 了,今天總結(jié)了一下python中對(duì)于字符串的逆序輸出的幾種常用
    的頭像 發(fā)表于 08-28 14:44 ?913次閱讀

    SQL 通用數(shù)據(jù)類型

    如何與存儲(chǔ)的數(shù)據(jù)進(jìn)行交互。 下面的表格列出了 SQL 中通用的數(shù)據(jù)類型: 數(shù)據(jù)類型 描述 CHARACTER(n) 字符/字符串。固定長(zhǎng)度 n。 VARCHAR(n) 或 CHARACTER VARYING(n) 字符/
    的頭像 發(fā)表于 08-18 09:46 ?677次閱讀

    為啥51單片機(jī)能搞,峰岹的就會(huì)報(bào)錯(cuò)呢?

    如圖圖1是stc系列單片機(jī)的代碼,發(fā)送字符串都可以,但是圖二峰岹的代碼發(fā)送字符串就不行,會(huì)報(bào)錯(cuò)
    發(fā)表于 07-09 13:39

    harmony-utils之StrUtil,字符串工具類

    harmony-utils之StrUtil,字符串工具類 harmony-utils 簡(jiǎn)介與說(shuō)明 [harmony-utils] 一款功能豐富且極易上手的HarmonyOS工具庫(kù),借助眾多實(shí)用工具類
    的頭像 發(fā)表于 07-03 11:32 ?493次閱讀

    STM32C031C6使用的是UART2通訊,通過(guò)printf()函數(shù)發(fā)送字符串時(shí),漢字錯(cuò)碼怎么解決?

    使用的是UART2通訊,通過(guò)printf()函數(shù)發(fā)送字符串時(shí),漢字錯(cuò)碼(見(jiàn)下圖),應(yīng)該是KEIL哪里沒(méi)有設(shè)置好的問(wèn)題。 啟用了UART2的中斷接收,可以接收到串口調(diào)試助手的數(shù)據(jù),但是緩存區(qū)的指針沒(méi)有歸零,下次接收時(shí)緩存區(qū)中的內(nèi)容接續(xù)(如下圖所示),不知道用什么命令來(lái)清除緩存區(qū)(即讓指針歸零)。
    發(fā)表于 03-07 12:30