字符串匹配的KMP算法

2017-12-22

例子说明

原字符串：BBC ABCDAB ABCDABCDABDE
查找串：ABCDABD

部分匹配表构造(共有元素的长度)

A            0 {}{}
AB           0 {A}{B}
ABC          0 {A AB} {C BC}
ABCD         0 {A AB ABC} {D CD BCD}
ABCDA        1 {A AB ABC ABCD} {A DA CDA BCDA}
ABCDAB       2 {A AB ABC ABCD ABCDA} {B AB DAB CDAB BCDAB}
ABCDABD      0 {A AB ABC ABCD ABCDA ABCDAB} {D BD ABD DABD CDABD BCDABD}

匹配过程

BBC ABCDAB ABCDABCDABDE
ABCDABD
 ABCDABD
  ABCDABD
   ABCDABD
    ABCDABD
        ABCDABD           # 6-2=4
          ABCDABD         # 2-0=2 
		    ABCDABD       # 6-2=4
               ABCDABD    # 匹配

参考