北京7月暑假班第2次課：回文子串-KMP等若干問題的討論鄒博市公開課特等獎(jiǎng)市賽課微課一等獎(jiǎng)?wù)n件

回文子串-KMP等若干問題討論

鄒博

年7月19日1第1頁字符串循環(huán)左移給定一個(gè)字符串S[0…N-1]，要求把S前k個(gè)字符移動(dòng)到S尾部，如把字符串“abcdef”前面2個(gè)字符‘a(chǎn)’、‘b’移動(dòng)到字符串尾部，得到新字符串“cdefab”：即字符串循環(huán)左移k。算法要求：時(shí)間復(fù)雜度為O(n)，空間復(fù)雜度為O(1)。2第2頁問題分析暴力移位法每次循環(huán)左移1位，調(diào)用k次即可時(shí)間復(fù)雜度O(kN)，空間復(fù)雜度O(1)三次拷貝S[0…k]→T[0…k]S[k+1…N-1]→S[0…N-k-1]T[0…k]→S[N-k…N-1]時(shí)間復(fù)雜度O(N)，空間復(fù)雜度O(k)3第3頁優(yōu)雅一點(diǎn)算法(X’Y’)’=YX如：abcdefX=abX’=baY=cdefY’=fedc(X’Y’)’=(bafedc)’=cdefab時(shí)間復(fù)雜度O(N)，空間復(fù)雜度O(1)4第4頁Code5第5頁字符串全排列給定字符串S[0…N-1]，設(shè)計(jì)算法，枚舉A全排列。6第6頁遞歸算法以字符串1234為例：1–2342–1343–2144–2317第7頁遞歸Code8第8頁假如字符有重復(fù)去除重復(fù)字符遞歸算法以字符1223為例：1–2232–1233–221帶重復(fù)字符全排列就是從第一個(gè)字符起每個(gè)數(shù)分別與它后面非重復(fù)出現(xiàn)數(shù)字交換。即：第i個(gè)數(shù)與第j個(gè)數(shù)交換時(shí)，要求[i,j)中沒有與第j個(gè)數(shù)相等數(shù)。9第9頁有重復(fù)字符遞歸10第10頁用空間換時(shí)間假如是單字符，能夠使用mark[256]假如是整數(shù)，能夠遍歷整數(shù)得到最大值max和最小值min，使用mark[max-min+1]假如是浮點(diǎn)數(shù)或者其它結(jié)構(gòu)數(shù)據(jù)，用Hash（實(shí)際上，假如發(fā)覺整數(shù)間改變太大，也應(yīng)該考慮使用Hash；而且，能夠認(rèn)為整數(shù)情況是最樸素Hash）11第11頁全排列非遞歸算法起點(diǎn)：字典序最小排列，比如12345終點(diǎn)：字典序最大排列，比如54321過程：從當(dāng)前排列生成字典序剛好比它大下一個(gè)排列如：21543下一個(gè)排列是23145怎樣計(jì)算？12第12頁21543下一個(gè)排列思索過程逐位考查哪個(gè)能增大一個(gè)數(shù)右面有比它大數(shù)存在，它就能增大那么最終一個(gè)能增大數(shù)是——x=11應(yīng)該增大到多少？增大到它右面比它大最小數(shù)——y=3應(yīng)該變?yōu)?3xxx顯然，xxx應(yīng)由小到大排：145得到2314513第13頁整理成算法語言步驟：后找、小大、交換、翻轉(zhuǎn)——查找字符串中最終一個(gè)升序位置i，即：S[k]>S[k+1](k>i)，S[i]<S[i+1]；查找S[i+1…N-1]中比Ai大最小值Sj；交換Si，Sj；翻轉(zhuǎn)S[i+1…N-1]交換操作后，S[i+1…N-1]一定是降序排列以926520為例，考查該算法正確性。14第14頁非遞歸算法Code15第15頁幾點(diǎn)說明下一個(gè)排列算法能夠天然去除重復(fù)字符問題C++STL已經(jīng)在Algorithm中集成了next_permutation能夠?qū)⒔o定在字符串A[0…N-1]首先升序排序，然后依次調(diào)用next_permutation直到返回false，即完成了非遞歸全排列算法。16第16頁求字符串最長回文子串回文子串定義：給定字符串str，若s同時(shí)滿足以下條件：s是str子串s是回文串則，s是str回文子串。該算法要求，是求str中最長那個(gè)回文子串。17第17頁解法1–枚舉中心位置intLongestPalindrome(constchar*s,intn){inti,j,max;if(s==0||n<1)return0;max=0;for(i=0;i<n;++i){//iisthemiddlepointofthepalindromefor(j=0;(i-j>=0)&&(i+j<n);++j)//ifthelengthofthepalindromeisoddif(s[i-j]!=s[i+j])break;if(j*2+1>max)max=j*2+1;for(j=0;(i-j>=0)&&(i+j+1<n);++j)//fortheevencaseif(s[i-j]!=s[i+j+1])break;if(j*2+2>max)max=j*2+2;}returnmax;}18第18頁算法解析step1——預(yù)處理因?yàn)榛匚拇衅鏀?shù)和偶數(shù)不一樣。判斷一個(gè)串是否是回文串，往往要分開編寫，造成代碼拖沓。一個(gè)簡單事實(shí)：長度為n字符串，共有n-1個(gè)“鄰接”，加上首字符前面，和末字符后面，更n+1“空”(gap)。所以，字符串本身和gap一起，共有2n+1個(gè)，必定是奇數(shù)；abbc→#a#b#b#c#aba→#a#b#a#所以，將待計(jì)算母串?dāng)U展成gap串，計(jì)算回文子串過程中，只考慮奇數(shù)匹配即可。19第19頁數(shù)組intP[size]字符串12212321→S[]="$#1#2#2#1#2#3#2#1#";用一個(gè)數(shù)組P[i]來統(tǒng)計(jì)以字符S[i]為中心最長回文子串向左/右擴(kuò)張長度（包含S[i]），比如S和P對應(yīng)關(guān)系：S#1#2#2#1#2#3#2#1#P12125214121612121P[i]-1恰好是原字符串中回文串總長度20第20頁分析算法關(guān)鍵我們?nèi)蝿?wù)：假定已經(jīng)得到了前i個(gè)值，考查i+1怎樣計(jì)算即：在P[0...i-1]已知前提下，計(jì)算P[i]值。換句話說，算法關(guān)鍵，是在P[0...i-1]已知前提下，能否給P[i]計(jì)算提供一點(diǎn)有用信息呢？1、經(jīng)過簡單遍歷，得到i個(gè)三元組{k,P[k],k+P[k]}，0≤k≤i-12、能夠挑選出這i個(gè)三元組中，k+P[k]最大那個(gè)三元組，不妨記做(id,P[id]，P[id]+id)。深入，為了簡化，記mx=P[id]+id，所以，得到三元組為(id,P[id],mx)，這個(gè)三元組含義非常顯著：全部i個(gè)三元組中，向右抵達(dá)最遠(yuǎn)位置，就是mx；3、在計(jì)算P[i]時(shí)候，考查i是否落在了區(qū)間[0,mx)中；4、若i在mx右側(cè)，說明[0,mx)沒有能夠控制住i，P[0..i-1]已知，無法給P[i]計(jì)算帶來有價(jià)值信息；5、若i在mx左側(cè)，說明[0,mx)控制（也有可能部分控制）了i，現(xiàn)在以圖示來詳細(xì)考查這種情況。21第21頁Manacher遞推關(guān)系記i關(guān)于id對稱點(diǎn)為j(=2*id-i)，若此時(shí)滿足條件mx-i>P[j]：記my為mx關(guān)于id對稱點(diǎn)(my=2*id-mx)；因?yàn)橐許[id]為中心最大回文子串為S[my+1…id…mx-1]，即：S[my+1…,id]與S[id,…,mx-1]對稱，而i和j關(guān)于id對稱，P[j]已知，所以P[i]=P[j]。22第22頁Manacher遞推關(guān)系記i關(guān)于id對稱點(diǎn)為j(=2*id-i)，若此時(shí)滿足條件mx-i＜P[j]：記my為mx關(guān)于id對稱點(diǎn)(my=2*id-mx)；因?yàn)橐許[id]為中心最大回文子串為S[my+1…id…mx-1]，即：S[my+1…,id]與S[id…,mx-1]對稱，而i和j關(guān)于id對稱，P[j]已知，所以P[i]最少等于mx-i（圖中綠色框部分）。23第23頁ManacherCode24第24頁關(guān)于原始算法主要改進(jìn)P[j]>mx–i：P[i]=mx–iP[j]<mx–i：P[i]=P[j]P[j]=mx–i：P[i]≥P[j]25第25頁Manacher改進(jìn)版26第26頁KMP算法串查找問題：給定原始串S和模式串P，查找從字符串S中第一次出現(xiàn)P位置。最基本字符串匹配算法——暴力爭解(Brute-Force)：O(m*n)；KMP算法是一個(gè)線性時(shí)間復(fù)雜字符串匹配算法，它是對BF算法改進(jìn)。BF算法時(shí)間復(fù)雜度O(strlen(S)*strlen(T))，空間復(fù)雜度O(1)。KMP算法時(shí)間復(fù)雜度O(strlen(S)+strlen(T))，空間復(fù)雜度O(strlen(T))。27第27頁暴力爭解28第28頁分析BF與KMP區(qū)分假設(shè)現(xiàn)在S串匹配到i位置，T串匹配到j(luò)位置。BF算法中，假如當(dāng)前字符匹配成功，即s[i+j]==T[j]，令i++，j++，繼續(xù)匹配下一個(gè)字符；假如失配，即S[i+j]!=T[j]，令i++，j=0，即每次匹配失敗情況下，模式串T相對于原始串S向右移動(dòng)了一位。KMP算法中，假如當(dāng)前字符匹配成功，即S[i+j]==T[j]，令i++，j++，繼續(xù)匹配下一個(gè)字符；假如失配，即S[i+j]!=T[j]，令i不變，j=next[j]，(next[j]<=j-1)，即模式串T相對于原始串S向右移動(dòng)了最少1位(移動(dòng)實(shí)際位數(shù)j-next[j]>=1),29第29頁描述性說法在暴力爭解中，為何模式串索引會回溯？因?yàn)槟Ｊ酱嬖谥貜?fù)字符假如模式串字符兩兩不相等呢？更弱一些條件：假如模式串首字符和其它字符不相等呢？對于Pj=p0p1...pj-1pj，查找字符串Pj最大相等k前綴和k后綴。即：查找滿足條件最大k，使得p0p1...pk-1pk=pj-kpj-k+1...pj-1pj30第30頁求模式串next模式串a(chǎn)baabcabanext-10011201231第31頁next遞推關(guān)系計(jì)算next函數(shù)方法能夠采取遞推，假如對于值ka0a1...ak-1ak=aj-kaj-k+1...aj-1aj則對于pattern前j+1序列字符，則若pattern[k+1]==pattern[j+1]next[j+1]=next(j)+1若pattern[k+1]≠pattern[j+1]記h=next[k]；假如此時(shí)pattern[h+1]==pattern[j+1],則next[j+1]=h+1不然重復(fù)此過程。32第32頁KMP33第33頁KMPCode34第34頁考查KMP時(shí)間復(fù)雜度我們考查模式串“串頭”和主串對應(yīng)位置（也就是暴力算法中i）。不匹配：串頭后移，確保盡快結(jié)束算法；匹配：串頭保持不動(dòng)（僅僅是i++、j++，但串頭和主串對應(yīng)位置沒變），但這個(gè)沒相關(guān)系。一旦發(fā)覺不匹配了地方，會跳過匹配過字符(next[j])。最壞情況，當(dāng)串頭位于N-M位置，算法結(jié)束所以，匹配時(shí)間復(fù)雜度為O(N)，算上計(jì)算nextO(M)時(shí)間，整體時(shí)間復(fù)雜度為O(M+N)。35第35頁KMP幾點(diǎn)說明網(wǎng)絡(luò)上有大量介紹KMP文章，在提供光芒思想同時(shí)，經(jīng)常有些不太準(zhǔn)確表述。需要自我區(qū)分。如：我們能夠預(yù)見KMP算法均攤復(fù)雜度是O(n+m)，為何呢？因?yàn)槟鉺串是不會回退，所以最多訪問了n次，而模式串pattern在每一次匹配中走動(dòng)均攤下來近似為O(m)，所以總復(fù)雜度為O(n+m)。這種解釋是不正確。該算法最經(jīng)濟(jì)實(shí)惠了解方法是編程實(shí)踐；經(jīng)典KMP有改進(jìn)算法，計(jì)算得到next數(shù)組能夠更小，使得模式串更加快向后匹配；BM算法等其它字符串快速匹配算法。36第36頁P(yáng)owerString問題給定一個(gè)長度為n字符串S，假如存在一個(gè)字符串T，重復(fù)若干次T，能夠得到S，那么，S叫做周期串，T叫做S一個(gè)周期。如：字符串a(chǎn)bababab是周期串，abab、ab都是它周期，其中，ab是它最小周期。設(shè)計(jì)一個(gè)算法，計(jì)算S最小周期。假如S不存在周期，返回空串。37第37頁使用next，線性時(shí)間處理問題計(jì)算Snext函數(shù)；記k=next[len-1]，p=len-k；若len能夠整除p，則p就是最小周期長度，前p個(gè)字符就是最小周期。怎樣證實(shí)？38第38頁BM算法Boyer-Moore算法是1977年，德克薩斯大學(xué)RobertS.Boyer教授和JStrotherMoore教授創(chuàng)造字符串匹配算法，擁有在最壞情況下O(N)時(shí)間復(fù)雜度，而且，在實(shí)踐中，比KMP算法實(shí)際效能高。BM算法不但效率高，而且構(gòu)思巧妙，輕易了解。39第39頁舉例說明BM算法運(yùn)行過程40第40頁壞字符首先，"字符串"與"搜索詞"頭部對齊，從尾部開始比較。這是一個(gè)很聰明想法，因?yàn)榧偃缥膊孔址黄ヅ洌敲粗灰淮伪容^，就能夠知道前7個(gè)字符必定不是要找結(jié)果。我們看到，"S"與"E"不匹配。這時(shí)，"S"就被稱為"壞字符"（badcharacter），即不匹配字符。我們還發(fā)覺，"S"不包含在搜索詞"EXAMPLE"之中，這意味著能夠把搜索詞直接移到"S"后一位。41第41頁壞字符引發(fā)模式滑動(dòng)依然從尾部開始比較，發(fā)覺"P"與"E"不匹配，所以"P"是"壞字符"。不過，"P"包含在搜索詞"EXAMPLE"之中。所以，將搜索詞后移兩位，兩個(gè)"P"對齊。42第42頁壞字符規(guī)則后移位數(shù)=壞字符位置-壞字符在搜索詞中最右出現(xiàn)位置假如"壞字符"不包含在搜索詞之中，則最右出現(xiàn)位置為-1以“P”為例，它作為“壞字符”，出現(xiàn)在搜索詞第6位（從0開始編號），在搜索詞中最右出現(xiàn)位置為4，所以后移6-4=2位。再以前面"S"為例，它出現(xiàn)在第6位，最右出現(xiàn)位置是-1（即未出現(xiàn)），則整個(gè)搜索詞后移6-(-1)=7位。43第43頁好后綴依次比較，得到“MPLE”匹配，稱為"好后綴"（goodsuffix），即全部尾部匹配字符串。注意，"MPLE"、"PLE"、"LE"、"E"都是好后綴。44第44頁碰到壞字符發(fā)覺“I”與“A”不匹配：“I”是壞字符。依據(jù)壞字符規(guī)則，此時(shí)搜索詞應(yīng)該后移2-(-1)=3位。問題是，有沒有更優(yōu)移法？45第45頁考慮好后綴46第46頁好后綴規(guī)則后移位數(shù)=好后綴位置-好后綴在搜索詞其余部分中最右出現(xiàn)位置假如好后綴在搜索詞中沒有再次出現(xiàn)，則為-1。全部“好后綴”（MPLE、PLE、LE、E）之中，只有“E”在“EXAMPL”之中出現(xiàn)，所以后移6-0=6位?！皦淖址?guī)則”只能移3位，“好后綴規(guī)則”能夠移6位。每次后移這兩個(gè)規(guī)則之中較大值。這兩個(gè)規(guī)則移動(dòng)位數(shù)，只與搜索詞相關(guān)，與原字符串無關(guān)。