?? da04.htm
字號:
lang=EN-US>011234567<span style='mso-spacerun:yes'> </span></span>改進后的<span
lang=EN-US>next</span>數組信息值為<span lang=EN-US>010101017</span>。<span lang=EN-US><o:p></o:p></span></span></p>
<p class=MsoNormal align=left style='text-align:left'><span lang=EN-US
style='font-family:宋體'>12</span><span style='font-family:宋體'>．<span lang=EN-US>011122312</span>。<span
lang=EN-US><o:p></o:p></span></span></p>
<p class=MsoNormal align=left style='text-align:left'><span lang=EN-US
style='font-family:宋體'>13</span><span style='font-family:宋體'>．<span lang=EN-US>next</span>定義見題上面<span
lang=EN-US>6</span>和下面題<span lang=EN-US>20</span>。串<span lang=EN-US>p</span>的<span
lang=EN-US>next</span>函數值為：<span lang=EN-US>01212345634</span>。<span
lang=EN-US><o:p></o:p></span></span></p>
<p class=MsoNormal align=left style='text-align:left'><span lang=EN-US
style='font-family:宋體'>14</span><span style='font-family:宋體'>．（<span
lang=EN-US>1</span>）<span lang=EN-US>S</span>的<span lang=EN-US>next</span>與<span
lang=EN-US>nextval</span>值分別為<span lang=EN-US>012123456789</span>和<span
lang=EN-US>002002002009</span>，<span lang=EN-US>p</span>的<span lang=EN-US>next</span>與<span
lang=EN-US>nextval</span>值分別為<span lang=EN-US>012123</span>和<span lang=EN-US>002003</span>。<span
lang=EN-US><o:p></o:p></span></span></p>
<p class=MsoNormal style='tab-stops:208.5pt'><span lang=EN-US style='font-family:
宋體'><span style='mso-spacerun:yes'> </span></span><span style='font-family:
宋體'>（<span lang=EN-US>2</span>）利用<span lang=EN-US>BF</span>算法的匹配過程：<span
lang=EN-US><span
style='mso-spacerun:yes'>
</span></span>利用<span lang=EN-US>KMP</span>算法的匹配過程：<span lang=EN-US><o:p></o:p></span></span></p>
<p class=MsoNormal align=left style='text-align:left;tab-stops:181.8pt'><span
lang=EN-US style='font-family:宋體'><span style='mso-spacerun:yes'> </span></span><span
style='font-family:宋體'>第一趟匹配：<span lang=EN-US> aabaabaabaac<span
style='mso-spacerun:yes'>
</span></span>第一趟匹配：<span lang=EN-US>aabaabaabaac<o:p></o:p></span></span></p>
<p class=MsoNormal align=left style='text-align:left'><span lang=EN-US
style='font-family:宋體'><span
style='mso-spacerun:yes'>
</span>aabaac(i=6,j=6)<span
style='mso-spacerun:yes'> </span><span
style='mso-spacerun:yes'> </span>aabaac(i=6,j=6)
<o:p></o:p></span></p>
<p class=MsoNormal style='tab-stops:166.5pt'><span lang=EN-US style='font-family:
宋體'><span style='mso-spacerun:yes'> </span></span><span style='font-family:
宋體'>第二趟匹配：<span lang=EN-US> aabaabaabaac<span
style='mso-spacerun:yes'>
</span></span>第二趟匹配：<span lang=EN-US>aabaabaabaac<o:p></o:p></span></span></p>
<p class=MsoNormal style='tab-stops:166.5pt'><span lang=EN-US style='font-family:
宋體'><span
style='mso-spacerun:yes'>
</span>aa(i=3,j=2)<span
style='mso-spacerun:yes'>
</span>(aa)baac <o:p></o:p></span></p>
<p class=MsoNormal style='tab-stops:166.5pt'><span lang=EN-US style='font-family:
宋體'><span style='mso-spacerun:yes'> </span></span><span style='font-family:
宋體'>第三趟匹配：<span lang=EN-US> aabaabaabaac<span
style='mso-spacerun:yes'>
</span></span>第三趟匹配：<span lang=EN-US>aabaabaabaac<o:p></o:p></span></span></p>
<p class=MsoNormal style='text-indent:57.0pt;mso-char-indent-count:5.0;
tab-stops:166.5pt'><span lang=EN-US style='font-family:宋體'><span
style='mso-spacerun:yes'>
</span>a(i=3,j=1)<span
style='mso-spacerun:yes'>
</span>(</span><span style='font-family:宋體'>成功<span lang=EN-US>) (aa)baac<o:p></o:p></span></span></p>
<p class=MsoNormal align=left style='text-align:left;text-indent:22.35pt;
mso-char-indent-count:1.96'><span style='font-family:宋體'>第四趟匹配：<span
lang=EN-US> aabaabaabaac<o:p></o:p></span></span></p>
<p class=MsoNormal align=left style='margin-left:11.4pt;mso-para-margin-left:
1.0gd;text-align:left;text-indent:45.6pt;mso-char-indent-count:4.0'><span
lang=EN-US style='font-family:宋體'><span
style='mso-spacerun:yes'>
</span>aabaac(i=9,j=6)<o:p></o:p></span></p>
<p class=MsoNormal align=left style='text-align:left;text-indent:22.35pt;
mso-char-indent-count:1.96'><span style='font-family:宋體'>第五趟匹配：<span
lang=EN-US> aabaabaabaac<o:p></o:p></span></span></p>
<p class=MsoNormal align=left style='margin-left:11.4pt;mso-para-margin-left:
1.0gd;text-align:left;text-indent:51.2pt;mso-char-indent-count:4.49'><span
lang=EN-US style='font-family:宋體'><span
style='mso-spacerun:yes'>
</span>aa(i=6,j=2)<o:p></o:p></span></p>
<p class=MsoNormal align=left style='text-align:left;text-indent:22.35pt;
mso-char-indent-count:1.96'><span style='font-family:宋體'>第六趟匹配：<span
lang=EN-US> aabaabaabaac<o:p></o:p></span></span></p>
<p class=MsoNormal align=left style='margin-left:11.4pt;mso-para-margin-left:
1.0gd;text-align:left;text-indent:45.6pt;mso-char-indent-count:4.0'><span
lang=EN-US style='font-family:宋體'><span
style='mso-spacerun:yes'>
</span>a(i=6,j=1)<o:p></o:p></span></p>
<p class=MsoNormal align=left style='text-align:left;text-indent:22.35pt;
mso-char-indent-count:1.96'><span style='font-family:宋體'>第七趟匹配：<span
lang=EN-US> aabaabaabaac<o:p></o:p></span></span></p>
<p class=MsoNormal align=left style='text-align:left;text-indent:33.5pt;
mso-char-indent-count:2.94'><span lang=EN-US style='font-family:宋體'>(</span><span
style='font-family:宋體'>成功<span lang=EN-US>)<span
style='mso-spacerun:yes'>
</span>aabaac(i=13,j=7)<o:p></o:p></span></span></p>
<p class=MsoNormal style='tab-stops:135.0pt'><span lang=EN-US style='font-family:
宋體'><span style='mso-spacerun:yes'> </span>15</span><span
style='font-family:宋體'>．（<span lang=EN-US>1</span>）<span lang=EN-US>p</span>的<span
lang=EN-US>nextval</span>函數值為<span lang=EN-US>0110132</span>。（<span lang=EN-US>p</span>的<span
lang=EN-US>next</span>函數值為<span lang=EN-US>0111232</span>）。<span lang=EN-US><o:p></o:p></span></span></p>
<p class=MsoNormal style='text-indent:27.0pt;tab-stops:135.0pt'><span
style='font-family:宋體'>（<span lang=EN-US>2</span>）利用<span lang=EN-US>KMP(</span>改進的<span
lang=EN-US>nextval)</span>算法，每趟匹配過程如下：<span lang=EN-US><o:p></o:p></span></span></p>
<p class=MsoNormal style='text-indent:27.0pt;tab-stops:135.0pt'><span
lang=EN-US style='font-family:宋體'><span style='mso-spacerun:yes'> </span></span><span
style='font-family:宋體'>第一趟匹配：<span lang=EN-US> abcaabbabcabaacbacba<o:p></o:p></span></span></p>
<p class=MsoNormal style='text-indent:27.0pt;tab-stops:135.0pt'><span
lang=EN-US style='font-family:宋體'><span
style='mso-spacerun:yes'>
</span>abcab(i=5,j=5)<o:p></o:p></span></p>
<p class=MsoNormal style='text-indent:27.0pt;tab-stops:135.0pt'><span
lang=EN-US style='font-family:宋體'><span style='mso-spacerun:yes'> </span></span><span
style='font-family:宋體'>第二趟匹配：<span lang=EN-US> abcaabbabcabaacbacba<o:p></o:p></span></span></p>
<p class=MsoNormal style='text-indent:27.0pt;tab-stops:135.0pt'><span
lang=EN-US style='font-family:宋體'><span
style='mso-spacerun:yes'>
</span>abc(i=7,j=3)<o:p></o:p></span></p>
<p class=MsoNormal style='text-indent:27.0pt;tab-stops:135.0pt'><span
lang=EN-US style='font-family:宋體'><span style='mso-spacerun:yes'> </span></span><span
style='font-family:宋體'>第三趟匹配：<span lang=EN-US> abcaabbabcabaacbacba<o:p></o:p></span></span></p>
<p class=MsoNormal style='text-indent:27.0pt;tab-stops:135.0pt'><span
lang=EN-US style='font-family:宋體'><span
style='mso-spacerun:yes'>
</span>a(i=7,j=1)<o:p></o:p></span></p>
<p class=MsoNormal style='text-indent:27.0pt;tab-stops:135.0pt'><span
lang=EN-US style='font-family:宋體'><span style='mso-spacerun:yes'> </span></span><span
style='font-family:宋體'>第四趟匹配：<span lang=EN-US> abcaabbabcabaac bacba<o:p></o:p></span></span></p>
<p class=MsoNormal style='text-indent:27.0pt;tab-stops:135.0pt'><span
lang=EN-US style='font-family:宋體'><span style='mso-spacerun:yes'>
</span>(</span><span style='font-family:宋體'>成功<span lang=EN-US>)<span
style='mso-spacerun:yes'>
</span><span style='mso-spacerun:yes'> </span>abcabaa(i=15,j=8)<o:p></o:p></span></span></p>
<p class=MsoNormal style='tab-stops:135.0pt'><span lang=EN-US style='font-family:
宋體'>16</span><span style='font-family:宋體'>．<span lang=EN-US>KMP</span>算法的時間復雜性是<span
lang=EN-US>O</span>（<span lang=EN-US>m+n</span>）。<span lang=EN-US><o:p></o:p></span></span></p>
<p class=MsoNormal style='text-indent:27.0pt;tab-stops:135.0pt'><span
lang=EN-US style='font-family:宋體'>p</span><span style='font-family:宋體'>的<span
lang=EN-US>next</span>和<span lang=EN-US>nextval</span>值分別為<span lang=EN-US>01112212321</span>和<span
lang=EN-US>01102201320</span>。<span lang=EN-US><o:p></o:p></span></span></p>
<p class=MsoNormal style='tab-stops:135.0pt'><span lang=EN-US style='font-family:
宋體'>17</span><span style='font-family:宋體'>．（<span lang=EN-US>1</span>）<span
lang=EN-US>p</span>的<span lang=EN-US>nextval</span>函數值為<span lang=EN-US>01010</span>。（<span
lang=EN-US>next</span>函數值為<span lang=EN-US>01123</span>）<span lang=EN-US><o:p></o:p></span></span></p>
<p class=MsoNormal style='margin-left:34.2pt;text-indent:-34.2pt;mso-char-indent-count:
-3.0;tab-stops:135.0pt'><span lang=EN-US style='font-family:宋體'><span
style='mso-spacerun:yes'> </span></span><span
style='font-family:宋體'>（<span lang=EN-US>2</span>）利用所得<span lang=EN-US>nextval</span>數值，手工模擬對<span
lang=EN-US>s</span>的匹配過程，與上面<span lang=EN-US>16</span>題類似，為節省篇幅，故略去。<span
lang=EN-US><o:p></o:p></span></span></p>
<p class=MsoNormal style='margin-left:34.2pt;text-indent:-34.2pt;mso-char-indent-count:
-3.0;tab-stops:135.0pt'><span lang=EN-US style='font-family:宋體'>18</span><span
style='font-family:宋體'>．模式串<span lang=EN-US>T</span>的<span lang=EN-US>next</span>和<span
lang=EN-US>nextval</span>值分別為<span lang=EN-US>0121123</span>和<span lang=EN-US>0021002</span>。<span
lang=EN-US><o:p></o:p></span></span></p>
<p class=MsoNormal style='tab-stops:135.0pt'><span lang=EN-US style='font-family:
宋體'>19</span><span style='font-family:宋體'>．第<span lang=EN-US>4</span>行的<span
lang=EN-US>p[J]=p[K]</span>語句是測試模式串的第<span lang=EN-US>J</span>個字符是否等于第<span
lang=EN-US>K</span>個字符，如是，則指針<span lang=EN-US>J</span>和<span lang=EN-US>K</span>均增加<span
lang=EN-US>1</span>，繼續比較。第<span lang=EN-US>6</span>行的<span lang=EN-US>p[J]=p[K]</span>語句的意義是，當第<span
lang=EN-US>J</span>個字符在模式匹配中失配時，若第<span lang=EN-US>K</span>個字符和第<span
lang=EN-US>J</span>個字符不等，則下個與主串匹配的字符是第<span lang=EN-US>K</span>個字符；否則，若第<span
lang=EN-US>K</span>個字符和第<span lang=EN-US>J</span>個字符相等，則下個與主串匹配的字符是第<span
lang=EN-US>K</span>個字符失配時的下一個（即<span lang=EN-US>NEXTVAL[K]</span>）。<span
lang=EN-US><o:p></o:p></span></span></p>
<p class=MsoNormal style='tab-stops:135.0pt'><span lang=EN-US style='font-family:
宋體'><span style='mso-spacerun:yes'> </span></span><span
style='font-family:宋體'>該算法在最壞情況下的時間復雜度<span lang=EN-US>O</span>（<span
lang=EN-US>m</span></span><sup><span lang=EN-US style='mso-bidi-font-size:10.5pt;
font-family:宋體'>2</span></sup><span style='font-family:宋體'>）。<span lang=EN-US><o:p></o:p></span></span></p>
<p class=MsoNormal style='tab-stops:135.0pt'><span lang=EN-US style='font-family:
宋體'>20</span><span style='font-family:宋體'>．（<span lang=EN-US>1</span>）當模式串中第一個字符與主串中某字符比較不等（失配）時，<span
lang=EN-US>next[1]=0</span>表示模式串中已沒有字符可與主串中當前字符<span lang=EN-US>s[i]</span>比較，主串當前指針應后移至下一字符，再和模式串中第一字符進行比較。<span
lang=EN-US><o:p></o:p></span></span></p>
<p class=MsoNormal style='tab-stops:135.0pt'><span lang=EN-US style='font-family:
宋體'><span style='mso-spacerun:yes'> </span></span><span
style='font-family:宋體'>（<span lang=EN-US>2</span>）當主串第<span lang=EN-US>i</span>個字符與模式串中第<span
lang=EN-US>j</span>個字符失配時，若主串<span lang=EN-US>i</span>不回溯，則假定模式串第<span
lang=EN-US>k</span>個字符與主串第<span lang=EN-US>i</span>個字符比較，<span lang=EN-US>k</span>值應滿足條件<span
lang=EN-US>1<k<j</span>并且‘<span lang=EN-US>p</span><sub>１</sub>…<span
lang=EN-US>p<sub>k-1</sub></span>’<span lang=EN-US>=</span>‘<span lang=EN-US>p<sub>j-k+1</sub></span>…<span
lang=EN-US>p<sub>j-1</sub></span>’，即<span lang=EN-US>k</span>為模式串向后移動的距離，<span
lang=EN-US>k</span>值有多個，為了不使向右移動丟失可能的匹配，<span lang=EN-US>k</span>要取大，由于<span
lang=EN-US>max{k}</span>表示移動的最大距離，所以取<span lang=EN-US>max{k}</span>，<span
lang=EN-US>k</span>的?? 快捷鍵說明
復制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號
Ctrl + =
減小字號
Ctrl + -