第四章字符串修改

第四章字符串 計(jì)算機(jī)學(xué)科中，字符串在諸如文本處理、生物計(jì)算中的DNA信息的提取等非數(shù)值應(yīng)用中有非常廣泛的作用。字符串是特殊的線性表，其特殊在元素受限（只允許字符作為元素），所以也稱它們?yōu)樵厥芟薜木€性表。字符串（String）概念字符串是組成元素（結(jié)點(diǎn)）為字符的線性表，簡(jiǎn)稱“串”。記作：s=“a0a1…an-1"字符串包含的字符個(gè)數(shù)稱為串長(zhǎng)。字符串（String）概念假設(shè)s1、s2兩個(gè)字符串，其中s1=a0a1…an-1，s2=b0b1…bm-1，0≤m≤n，如果存在整數(shù)i(0≤i≤n-m)，使得對(duì)任意j=0,1,…,m-1，都有bj=ai+j同時(shí)成立，則稱字符串s2是字符串s1的子串，或稱包含。字符串（String）概念長(zhǎng)度為零的串稱為空串，不包含任何字符。注意：區(qū)分空串和空白串 空串不包括任何字符，空白串包括空格符等不可見字符?？沾侨魏巫址淖哟魏未际瞧渥陨淼淖哟?。字符串（String）字符串與一般線性表相比特殊在：字符串的數(shù)據(jù)對(duì)象（元素）約束為字符集中的字符；主要的字符集有ASCII和UNICODE一般線性表的基本操作大多以“單個(gè)元素”為操作對(duì)象，而字符串的基本操作通常以“串整體”為操作對(duì)象。字符串邏輯定義字符串的數(shù)據(jù)元素及其關(guān)系元素——任意合法字符類型的數(shù)據(jù)；關(guān)系——唯一前驅(qū)唯一后繼；字符串的操作在字符串的尾端添加字符、串連接、串復(fù)制、串比較、在串中搜索給定的字符或子串。//字符串抽象類定義template<classT>classString{ public: intlength(); boolisEmpty();

voidclear(); stringappend(constcharc); stringconcatenate(constchar*s);

stringcopy(constchar*s);

stringinsert(constcharc,constintindex);

stringfind(constcharc,constintstart);

stringsubstr(constints,constintlen);}字符串物理實(shí)現(xiàn)存儲(chǔ)結(jié)構(gòu)：順序存儲(chǔ)結(jié)構(gòu)（順序字符串）

鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)（鏈?zhǔn)阶址┳址\(yùn)算：模式匹配字符串順序存儲(chǔ)方式 字符串的順序存儲(chǔ)結(jié)構(gòu)，具體又可分為靜態(tài)和動(dòng)態(tài)兩種情況。其共同特點(diǎn)為：使用空間： 一塊連續(xù)的存儲(chǔ)空間關(guān)系表示： 物理相鄰表示邏輯相鄰元素訪問： 通過下標(biāo)（相對(duì)地址）讀寫字符串順序存儲(chǔ)方式 字符串（線性表）的順序存儲(chǔ)方式最少需要表示兩方面的信息：記錄分配給串的連續(xù)空間首地址＋長(zhǎng)度連續(xù)空間的當(dāng)前使用情況當(dāng)前表長(zhǎng)字符串順序存儲(chǔ)方式對(duì)于當(dāng)前使用情況有兩種表示方式：加一個(gè)特殊的末尾標(biāo)記，如：’\0’記錄串長(zhǎng)度用S[0]作為記錄串長(zhǎng)的存儲(chǔ)單元 缺點(diǎn)：串的最大長(zhǎng)度不能超過256另辟一個(gè)整型存儲(chǔ)單元存儲(chǔ)串的長(zhǎng)度字符串順序存儲(chǔ)方式對(duì)于分配給串的連續(xù)空間有兩種實(shí)現(xiàn)方式固定長(zhǎng)度連續(xù)空間——靜態(tài)順序存儲(chǔ) 空間長(zhǎng)度在定義是確定，使用期間空間大小不變；可變長(zhǎng)度連續(xù)空間——?jiǎng)討B(tài)順序存儲(chǔ) 空間長(zhǎng)度在定義是確定，使用期間空間可以根據(jù)需要擴(kuò)充。字符串順序存儲(chǔ)方式字符串的靜態(tài)順序存儲(chǔ)兩種實(shí)現(xiàn)方式：利用數(shù)組和整型常量利用指針和動(dòng)態(tài)內(nèi)存分配字符串順序存儲(chǔ)方式串的靜態(tài)順序存儲(chǔ)——利用數(shù)組constintMsize=100;template<classT>classS1_arrString{ T s[Msize]; //以‘/0’為串結(jié)束符 //int curlen;public:

…}字符串順序存儲(chǔ)方式串的靜態(tài)順序存儲(chǔ)——利用數(shù)組（例）c/c++語言標(biāo)準(zhǔn)字符串是采用的靜態(tài)順序存儲(chǔ)方案的典型代表。其特點(diǎn)是 直接采用字符數(shù)組存儲(chǔ)字符串，chars[M]; 串長(zhǎng)最大不能超過M-1，以‘/0’作為串結(jié)束標(biāo)記標(biāo)準(zhǔn)庫<string.h>(C)/<cstring.h>(C++)提供了處理串的函數(shù).1.串長(zhǎng) intstrlen(char*s);2.串復(fù)制 char*strcpy(char*s1,char*s2);3．串拼接 char*strcat(char*s1,char*s2);4．串比較 intstrcmp(char*s1,char*s2);5．輸入和輸出函數(shù)6．定位函數(shù)

char*strchr(char*s,charc);7．右定位函數(shù)char*strrchr(char*s,charc);//標(biāo)準(zhǔn)串運(yùn)算實(shí)現(xiàn)——串比較intstrcmp(constchar*s1,constchars2){inti=0;while(s2[i]!=‘\0’||s1[i]!=‘\0’){if(s1[i]>s2[i])return1;else if(s1[i]<s2[i])return-1;i++;}if(s1[i]==‘\0’&&s2[i]!=‘\0’)return-1;else if(s1[i]!=‘\0’&&s2[i]==‘\0’)return1; else retrun0;}字符串順序存儲(chǔ)方式串的靜態(tài)順序存儲(chǔ)——利用指針template<classT>classS2_arrString{ T *s; //以‘/0’為串結(jié)束符int msize; //int curlen;public:

…}字符串順序存儲(chǔ)方式串的靜態(tài)順序存儲(chǔ)——評(píng)價(jià)適合訪問/查找串中單個(gè)字符或連續(xù)的一組字符子串；進(jìn)行插入和刪除（增減字符）操作效率差，需要移動(dòng)插入或刪除點(diǎn)后面的所有字符；由于存儲(chǔ)串的數(shù)組是靜態(tài)定長(zhǎng)的，可能在操作中出現(xiàn)溢出。字符串順序存儲(chǔ)方式字符串的動(dòng)態(tài)順序存儲(chǔ)——利用指針template<classT>classarrString{ T *str; //以‘/0’為串結(jié)束符int size;public: …}字符串順序存儲(chǔ)方式疑問：它和利用指針實(shí)現(xiàn)的靜態(tài)順序存儲(chǔ)有什么區(qū)別？數(shù)據(jù)成員上沒有區(qū)別，函數(shù)成員有區(qū)別靜態(tài)方式在操作中串空間不足時(shí)，直接溢出結(jié)束；動(dòng)態(tài)方式在串空間不足時(shí)會(huì)，給串空間進(jìn)行動(dòng)態(tài)擴(kuò)充，當(dāng)擴(kuò)充失敗才溢出結(jié)束。s1str:size:5……Hello\0012345s1str:size:10……Hello\0012345Helloworld\001234567891011字符串順序存儲(chǔ)方式字符串順序存儲(chǔ)方式串的動(dòng)態(tài)順序存儲(chǔ)（例）c++語言除了標(biāo)準(zhǔn)字符串之外，還提供了String類，是采用的動(dòng)態(tài)順序存儲(chǔ)方案。根據(jù)需要申請(qǐng)空間；以‘/0’作為串結(jié)束標(biāo)記；下面給出String類的定義和部分函數(shù)的實(shí)現(xiàn)//動(dòng)態(tài)順序存儲(chǔ)類定義template<classcharT>classString{private: charT* str;int size;public://創(chuàng)建新字符串String(char*s=‘’); //以標(biāo)準(zhǔn)字符串s拷貝為初值String(Strings); //以標(biāo)準(zhǔn)字符串s拷貝為初值//銷毀本串，從計(jì)算機(jī)存儲(chǔ)空間刪去本串~String();//賦值操作=String&operator=(char*s); //標(biāo)準(zhǔn)串s拷貝到本串String&operator=(String&s); //串s復(fù)制到本串//拼接函數(shù)＋Stringoperator＋(char*s); //本串拼接標(biāo)準(zhǔn)串s

Stringoperator＋(String&s); //本串拼接串s

//友函數(shù)作為拼接函數(shù)+其返回值是一個(gè)實(shí)例串//等于標(biāo)準(zhǔn)串str拼接串sfriendStringoperator+(char*s1,String&s);//‘關(guān)系’函數(shù)，用于比較相等、大、小，例如intoperator<(char*s); //本串小于標(biāo)準(zhǔn)串s返回非0intoperator<(String&s); //本串小于串s返回非0

friendintoperator<(char*s1,String&s);//友元函數(shù)

//‘輸入輸出’函數(shù)>>和<<以及讀子串等，例如友函數(shù)friendistream&operator>>(isteream&istr,String&s);friendostream&operator<<(osteream&istr,String&s);//‘子串函數(shù)’：插入子串、尋找子串、//提取子串、刪除子串等，例如StringSubstr(intindex，intcount);//‘串與字符’函數(shù)：按字符定位等，例如//在本串中尋找字符c,從下標(biāo)start開始找,//尋找到c后,返回字符c在本串的下標(biāo)位置intFind(charc,intstart);//其他函數(shù)：求串長(zhǎng)、判空串、清為空串、intstrlen(); //返回本串的當(dāng)前串長(zhǎng)intIsEmpty(); //判本串為空串?voidclear(); //清本串為空串};//動(dòng)態(tài)順序存儲(chǔ)類定義template<classcharT>classString{private: charT* str;int size;public://創(chuàng)建新字符串String(char*s=‘’); //以標(biāo)準(zhǔn)字符串s拷貝為初值String(Strings); //以標(biāo)準(zhǔn)字符串s拷貝為初值//銷毀本串，從計(jì)算機(jī)存儲(chǔ)空間刪去本串~String();//賦值操作=String&operator=(char*s); //標(biāo)準(zhǔn)串s拷貝到本串String&operator=(String&s); //串s復(fù)制到本串//拼接函數(shù)＋Stringoperator＋(char*s); //本串拼接標(biāo)準(zhǔn)串s

Stringoperator＋(String&s); //本串拼接串s

//友函數(shù)作為拼接函數(shù)+其返回值是一個(gè)實(shí)例串//等于標(biāo)準(zhǔn)串str拼接串sfriendStringoperator+(char*s1,String&s);//‘關(guān)系’函數(shù)，用于比較相等、大、小，例如intoperator<(char*s); //本串小于標(biāo)準(zhǔn)串s返回非0intoperator<(String&s); //本串小于串s返回非0

friendintoperator<(char*s1,String&s);//友元函數(shù)

//‘輸入輸出’函數(shù)>>和<<以及讀子串等，例如友函數(shù)friendistream&operator>>(isteream&istr,String&s);friendostream&operator<<(osteream&istr,String&s);//‘子串函數(shù)’：插入子串、尋找子串、//提取子串、刪除子串等，例如StringSubstr(intindex，intcount);//‘串與字符’函數(shù)：按字符定位等，例如//在本串中尋找字符c,從下標(biāo)start開始找,//尋找到c后,返回字符c在本串的下標(biāo)位置intFind(charc,intstart);//其他函數(shù)：求串長(zhǎng)、判空串、清為空串、intstrlen(); //返回本串的當(dāng)前串長(zhǎng)intIsEmpty(); //判本串為空串?voidclear(); //清本串為空串};//動(dòng)態(tài)順序存儲(chǔ)類定義template<classcharT>classString{private: charT* str;int size;public://創(chuàng)建新字符串String(char*s=‘’); //以標(biāo)準(zhǔn)字符串s拷貝為初值String(Strings); //以標(biāo)準(zhǔn)字符串s拷貝為初值//銷毀本串，從計(jì)算機(jī)存儲(chǔ)空間刪去本串~String();//賦值操作=String&operator=(char*s); //標(biāo)準(zhǔn)串s拷貝到本串String&operator=(String&s); //串s復(fù)制到本串//拼接函數(shù)＋Stringoperator＋(char*s); //本串拼接標(biāo)準(zhǔn)串s

Stringoperator＋(String&s); //本串拼接串s

//友函數(shù)作為拼接函數(shù)+其返回值是一個(gè)實(shí)例串//等于標(biāo)準(zhǔn)串str拼接串sfriendStringoperator+(char*s1,String&s);//‘關(guān)系’函數(shù)，用于比較相等、大、小，例如intoperator<(char*s); //本串小于標(biāo)準(zhǔn)串s返回非0intoperator<(String&s); //本串小于串s返回非0

friendintoperator<(char*s1,String&s);//友元函數(shù)

//‘輸入輸出’函數(shù)>>和<<以及讀子串等，例如友函數(shù)friendistream&operator>>(isteream&istr,String&s);friendostream&operator<<(osteream&istr,String&s);//‘子串函數(shù)’：插入子串、尋找子串、//提取子串、刪除子串等，例如StringSubstr(intindex，intcount);//‘串與字符’函數(shù)：按字符定位等，例如//在本串中尋找字符c,從下標(biāo)start開始找,//尋找到c后,返回字符c在本串的下標(biāo)位置intFind(charc,intstart);//其他函數(shù)：求串長(zhǎng)、判空串、清為空串、intstrlen(); //返回本串的當(dāng)前串長(zhǎng)intIsEmpty(); //判本串為空串?voidclear(); //清本串為空串};//構(gòu)造實(shí)現(xiàn)template<classcharT>String::String(char*s=‘’){ size=strlen(s);str=newchar[size+1];assert(str!=‘\0’);strcpy(str,s);}作用相當(dāng)于：

if(str!=‘\0’)

return;字符串順序存儲(chǔ)方式取子串函數(shù)實(shí)現(xiàn)pos+len-1

curLen-1pos+len-1

curLen//取子串函數(shù)實(shí)現(xiàn)template<classcharT>StringString::Substr(intpos,intn){inti;intleft=size–pos;Stringtmp;char*p,*q;if(pos>=size) returnNULL;if(n>=left) n=left;delete[]tmp.str;tmp.str=newchar[n+1];assert(tmp.str!=NULL);p=tmp.str;q=&str[pos];for(i=0;i<n;i++)*p++=*q++;*p=‘\0’;tmp.size=n;returntmp;}//取子串函數(shù)實(shí)現(xiàn)template<classcharT>StringString::Substr(intpos,intn){inti;intleft=size–pos;Stringtmp;char*p,*q;if(pos>=size) returnNULL;if(n>=left) n=left;delete[]tmp.str;tmp.str=newchar[n+1];assert(tmp.str!=NULL);p=tmp.str;q=&str[pos];for(i=0;i<n;i++)*p++=*q++;*p=‘\0’;tmp.size=n;returntmp;}字符串順序存儲(chǔ)方式作業(yè)實(shí)現(xiàn)string類的其它成員函數(shù)注意：其數(shù)據(jù)成員str的空間使用問題字符串鏈?zhǔn)酱鎯?chǔ)方式 鏈串是變長(zhǎng)非順序存儲(chǔ)結(jié)構(gòu)。單鏈表、雙向鏈表、循環(huán)鏈表和靜態(tài)鏈表等線性表實(shí)現(xiàn)結(jié)構(gòu)都可以用于實(shí)現(xiàn)鏈?zhǔn)酱?，一般使用的是帶頭結(jié)點(diǎn)的單鏈表。使用空間： 連續(xù)/非連續(xù)的存儲(chǔ)空間關(guān)系表示： 指針/下標(biāo)（靜態(tài)鏈表）元素訪問： 通過指針/下標(biāo)讀寫字符串鏈?zhǔn)酱鎯?chǔ)方式用單鏈表方式來存儲(chǔ)串值，串的這種鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)簡(jiǎn)稱為鏈串。其結(jié)點(diǎn)結(jié)構(gòu)為：一個(gè)鏈串由頭指針唯一確定。classnode{ char data; node *next;};字符串鏈?zhǔn)酱鎯?chǔ)方式鏈串評(píng)價(jià)優(yōu)點(diǎn) 解決了順序串上的插入和刪除操作不方便，需要移動(dòng)大量的字符的問題；缺點(diǎn) 存儲(chǔ)空間利用率太低。字符串鏈?zhǔn)酱鎯?chǔ)方式改進(jìn)鏈串為提高存儲(chǔ)密度，可使每個(gè)結(jié)點(diǎn)存放多個(gè)字符通常將結(jié)點(diǎn)數(shù)據(jù)域存放的字符個(gè)數(shù)定義為結(jié)點(diǎn)的大小；顯然，當(dāng)結(jié)點(diǎn)大小大于1時(shí)，串的長(zhǎng)度不一定正好是結(jié)點(diǎn)的整數(shù)倍，因此要用特殊字符(‘\0’)來填充最后一個(gè)結(jié)點(diǎn)，以表示串的終結(jié)。字符串鏈?zhǔn)酱鎯?chǔ)方式改進(jìn)鏈串——實(shí)現(xiàn)對(duì)于結(jié)點(diǎn)大小不為1的鏈串，其類型定為義只需對(duì)上述的結(jié)點(diǎn)類型做簡(jiǎn)單的修改即可。constintnodesize=80;classnode{ chardata[nodesize]; node*next;};字符串鏈?zhǔn)酱鎯?chǔ)方式改進(jìn)鏈串——評(píng)價(jià)優(yōu)點(diǎn)是提高空間利用率；問題是單個(gè)結(jié)點(diǎn)所包含的字符個(gè)數(shù)的確定設(shè)置過大有可能變?yōu)轫樞虼鎯?chǔ)，小了空間利用率提高不明顯。設(shè)置的一般規(guī)律是當(dāng)串長(zhǎng)較大時(shí)結(jié)點(diǎn)可適當(dāng)設(shè)大一些，反之設(shè)小一些。字符串存儲(chǔ)方式總結(jié):當(dāng)字符串臨時(shí)存儲(chǔ)時(shí)，使用順序存儲(chǔ)當(dāng)字符串長(zhǎng)期存儲(chǔ)時(shí)（文件），使用鏈?zhǔn)酱鎯?chǔ)（鏈結(jié)點(diǎn)為物理塊）。字符串的模式匹配子串定位運(yùn)算（主串中找子串位置）又稱為模式匹配(PatternMatching)或串匹配(StringMatching)在串匹配中，一般將主串稱為目標(biāo)串，子串稱之為模式串。字符串的模式匹配此運(yùn)算的應(yīng)用——非常廣泛典型的例子有文本編輯和DNA分析。例如，在文本編輯程序中，我們經(jīng)常要查找某一特定單詞在文本中出現(xiàn)的位置。顯然，解此問題的有效算法能極大地提高文本編輯程序的響應(yīng)性能。字符串的模式匹配模式匹配分類精確匹配（exactmatching）近似匹配（approximatematching）字符串的模式匹配模式匹配分類——精確匹配定義 如果在目標(biāo)T中至少一處存在模式P，則稱匹配成功，否則即使目標(biāo)與模式只有一個(gè)字符不同也不能成為匹配成功，即匹配失敗。字符串的模式匹配模式匹配分類——精確匹配模式串可以是多種形式：?jiǎn)芜x（不帶有通配符），如：set;多選（帶有通配符），如：s?t;復(fù)雜的模式可以采用正則表達(dá)式。本節(jié)的模式不涉及通配符和正則表達(dá)式字符串的模式匹配模式匹配分類——近似匹配如果模式P與目標(biāo)T（或其子串）存在某種程度的相似，則認(rèn)為匹配成功。常用的衡量字符串相似度的方法是根據(jù)一個(gè)串轉(zhuǎn)換成另一個(gè)串所需的的基本操作的數(shù)目來確定的?；静僮饔勺址牟迦?、刪除和替換來組成本節(jié)的模式不涉及近似匹配字符串的模式匹配模式匹配(patternmatching)已知：一個(gè)目標(biāo)對(duì)象T（字符串）一個(gè)模板（pattern）P（字符串）任務(wù)：求出T中第一個(gè)與P全同匹配的子串（簡(jiǎn)稱為“配串”），返回其首字符位置字符串的模式匹配 T t0t1…titi+1ti+2…ti+m-2ti+m-1…tn-1 ‖‖‖‖‖ P

p0p1p2…pm-2pm-1為使模式P與目標(biāo)T匹配，必須滿足：p0p1p2…pm-1=titi+1ti+2…ti+m-1字符串的模式匹配字符串的模式匹配算法主要有兩種：樸素模式匹配算法KMP模式匹配算法樸素模式匹配樸素的模式匹配算法的基本思想窮舉即：將目標(biāo)串中所有與模式串等長(zhǎng)的子串都比較一遍。T=P=ababababababbabababbabababbabababbabababbabababbabababbabababbXXXXXX√//樸素模式匹配#include<String.h>#include<assert.h>intNaiveStrMatching(constString&T,constString&P){inti=0;intj=0;intpLen=P.length();inttLen=T.length();if(tLen<pLen)return(-1);while(i<pLen&&j<tLen){if(T[j]==P[i]) i++,j++;else{ j=j–i+1;i=0;}}if(i>=pLen)return(j–pLen+1);elsereturn(-1);}//樸素模式匹配#include<String.h>#include<assert.h>intNaiveStrMatching(constString&T,constString&P){inti=0;intj=0;intpLen=P.length();inttLen=T.length();if(tLen<pLen)return(-1);while(i<pLen&&j<tLen){if(T[j]==P[i]) i++,j++;else{ j=j–i+1;i=0;}}if(i>=pLen)return(j–pLen+1);elsereturn(-1);}樸素模式匹配樸素模式匹配最佳示例比較|P|次，時(shí)間代價(jià)O(|P|)01234567890123456789aaaaaaaaaaaaaaaaaaabaaaaa評(píng)價(jià)不同情況下樸素模式匹配算法的比較次數(shù)不同即時(shí)間代價(jià)不同。樸素模式匹配樸素模式匹配失敗最佳示例比較(|T|-|P|+1)次，時(shí)間代價(jià)O(|T|-|P|+1)01234567890123456789aaaaaaaaaaaaaaaaaaabhhhhbhhhhbhhhhb……h(huán)hhhb評(píng)價(jià)樸素模式匹配樸素模式匹配最差佳示例比較|P|(|T|-|P|+1)次，時(shí)間代價(jià)O(|T||P|)01234567890123456789aaaaaaaaaaaaaaaaaaabaaaabaaaabaaaab……aaaab評(píng)價(jià)樸素模式匹配評(píng)價(jià)最壞情況下的時(shí)間復(fù)雜度為O(|T||P|)。這種最壞的情況很少出現(xiàn)在文本中，經(jīng)常出現(xiàn)在DNA信息或圖像信息中。能否改進(jìn)？樸素模式匹配改進(jìn)理論上的推導(dǎo)利用目標(biāo)和模式串中字符的分布概率可以估算出平均比較次數(shù)為：2(|T|-|P|+1)<2|T|利用馬爾可夫鏈（MarkovChain）的有關(guān)理論，可以估算出更好的平均比較次數(shù)為(|A||P|+1-|A|)/(|A|-1)其中，|A|是字符串中允許使用的字符個(gè)數(shù)012345678901234567Tabacaabaccabacabaa1abacab2abacab3abacab4abacab5abacab6abacab7abacab8abacab9abacab10abacab11abacab0123456789Tabacaabacc1abacab2abacab3abacab4abacab5abacab樸素模式匹配改進(jìn)信息在樸素模式匹配的比較過程中有一部分字符之間的比較可以轉(zhuǎn)換成模式串自身字符和自身字符的比較。而模式串自身字符之間的比較可以通過事先處理模式串，從而事先確知它們的比較結(jié)果，從而減少匹配時(shí)的比較次數(shù)。樸素模式匹配改進(jìn)什么時(shí)候可以利用模式串自身和自身字符關(guān)系來減少比較的次數(shù)？我們來考慮一般情況下的情況，假設(shè)：目標(biāo)串T和模式串P從Tj-i出開始匹配到Tj處發(fā)生失配。樸素模式匹配改進(jìn) T T0T1…Tj-i-1Tj-iTj-i+1…Tj-2Tj-1Tj…Tn-1

‖‖‖‖ P P0P1…Pi-2Pi-1Pi

則有：Tj-iTj-i+1…Tj-1=P0P1…Pi-1(1)樸素模式匹配改進(jìn)如果P0P1…Pi-2=P1P2…Pi-1(2)

則立刻可以斷定P0P1…Pi-2

=Tj-i+1Tj-i+2…Tj-1

此時(shí)直接比較Pi-1和Tj即可。（相當(dāng)于將模式串右移一位繼續(xù)比較）樸素模式匹配改進(jìn)…Tj-iTj-i+1…Tj-2Tj-1TjTj+1…P0P1…Pi-2Pi-1Pi…P0…Pi-1Pi-2Pi-1Pi…====X樸素模式匹配改進(jìn)

如果(2)不成立，即P0P1…Pi-2

P1P2…Pi-1

則繼續(xù)考慮P0P1…Pi-3

=P2P3…Pi-1 (3)

若成立直接比較Pi-2和Tj即可。（相當(dāng)于將模式串右移兩位繼續(xù)比較）樸素模式匹配改進(jìn)…Tj-iTj-i+1…Tj-2Tj-1TjTj+1…P0P1P2…Pi-3Pi-2Pi-1Pi…P0P1P2…Pi-3Pi-2Pi-1Pi…=====X樸素模式匹配改進(jìn)

如果(3)不成立，即P0P1…Pi-3

P2P3…Pi-1

則繼續(xù)考慮

P0P1…Pi-4

=P3P4…Pi-1 (3)

以此類推樸素模式匹配改進(jìn)直到對(duì)于某一個(gè)“k”值，使得P0P1…Pi-k-1=PkPk+1…Pi-1成立，此時(shí)將模式串右移k位繼續(xù)比較Pi-k和Tj即可。樸素模式匹配改進(jìn)…Tj-iTj-i+1…Tj-2Tj-1TjTj+1…P0P1…Pi-k-1Pi-k…PkPk+1…Pi-1Pi…P0P1…Pi-k-1Pi-k…PkPk+1…Pi-1Pi…====X樸素模式匹配改進(jìn)特別的： k最大可以等于i，這是意味著不存在這樣相等的子串，直接移動(dòng)i位繼續(xù)比較P0和Tj即可?！璗j-iTj-i+1…Tj-2Tj-1TjTj+1…P0P1P2…Pi-3Pi-2Pi-1Pi…X樸素模式匹配改進(jìn)結(jié)論由此可見，根據(jù)模式串本身的特征，就可以確定在某趟發(fā)生發(fā)生失配時(shí)模式串應(yīng)該右移的位數(shù)，在失配處開始下趟匹配。這樣既保證不丟失匹配串，又不需要在目標(biāo)串回溯，從而消除冗余比較。樸素模式匹配改進(jìn)當(dāng)模式串在某字符處失配時(shí)，如何確定模式串右移的位數(shù)（或移至哪一位）？由于模式串的每一個(gè)字符都有可能在匹配過程中失配，所以使用字符串的特征向量 來表示。字符串的特征向量預(yù)備定義把P的前k個(gè)字符組成的子串P(0...k-1)稱為P的前綴子串（也稱“串首”）；把P在i之前的k個(gè)字符組成的子串P(i-k...i-1)稱為i位置的后綴子串（也稱“尾串‘）。字符串的特征向量定義設(shè)：模式串中P(0...i-1)存在最長(zhǎng)為k的前綴子串和后綴子串相等；當(dāng)i位置的字符Pi與主串中字符Tj失配時(shí)，則模式串的下標(biāo)從位置i移動(dòng)到位置k（向右移動(dòng)了i-k位），讓Pk與Tj繼續(xù)比較；我們將k稱為字符Pi的特征數(shù)，記為ni；字符串的特征向量特征向量整個(gè)模式串所有字符的特征數(shù)合稱為模式串的特征向量，記為next。計(jì)算公式字符串的特征向量特征向量問題：該公式的計(jì)算效率比較低？因?yàn)闉榱苏业絢值，需要不斷的判斷P(0‥k-1)和P(i-k‥i-1)是否相等，這個(gè)判斷過程相當(dāng)于進(jìn)行樸素模式匹配。字符串的特征向量改進(jìn)的特征向量計(jì)算我們注意到當(dāng)計(jì)算next[i]時(shí)，next[0‥i-1]都已計(jì)算完成，而為了計(jì)算next[i]而進(jìn)行的P(0‥k-1)和P(i-k‥i-1)的比較，完全可以利用next[0‥i-1]來計(jì)算。即：利用next[0‥i-1]計(jì)算next[i]

。改進(jìn)的特征向量計(jì)算——next[i]的遞歸定義如果i=0，則next[i]=-1；令k=next[i-1]

，如果i>01、如果Pi-1=Pk，則next[i]=k+1；2、如果Pi-1

≠Pk&&

k≠0，令k=next[k]如果Pi-1=Pk

，則轉(zhuǎn)1處理；如果k=0，則轉(zhuǎn)3處理；否則，轉(zhuǎn)2處理；3、如果Pi-1

≠Pk&&k=0，則next[i]=0。例：計(jì)算模式串”abcdaabcab”的next數(shù)組字符串的特征向量0123456789Pabcdaabcabnext-1000011231字符串的特征向量再改進(jìn)next在利用next進(jìn)行模式匹配時(shí)，當(dāng)有Pi

≠Tj，則應(yīng)轉(zhuǎn)向Pnext[i]

與Tj繼續(xù)比較；如果有Pi=Pnext[i]，則Pnext[i]

≠Tj必然成立，則可將next[i]

修改為next[next[i]]。如果還相等則繼續(xù)利用next向前推，直至-1為止字符串的特征向量0123456789Pabcdaabcabnext-10000112310123456789Pabcdaabcabnext-1000-110030//特征向量計(jì)算#include<String.h>#include<assert.h>int*findNext(StringP){inti=0;intk=-1;intm=P.length();assert(m=0);int*next=nextint[m];assert(next!=0);next[0]=-1;while(i<m){ while(k>=0&&P[i]!=P[k]) k=next[k]; i++; k++; if(i==m) break; if(P[i]==P[k]) next[i]=next[k]; else next[i]=k;}returnnext;}//特征向量計(jì)算#include<String.h>#include<assert.h>int*findNext(StringP){inti=0;intk=-1;intm=P.length();assert(m=0);int*next=nextint[m];assert(next!=0);next[0]=-1;while(i<m){ while(