设主串 T = abaabaabcabaabc,模式串 S = abaabc,采用 KMP 算法进行模式匹配,到匹配成功时为止,在匹配过程中进行的单个字符间的比较次数是: A. 9 B. 10 C. 12 D. 15
时间: 2024-05-29 18:10:58 浏览: 167
KMP算法的核心是求出模式串的next数组,根据next数组进行匹配。先求出next数组:
模式串:abaabc
next数组:-1, 0, 0, 1, 1, 0
接下来进行匹配:
T:a b a a b a a b c a b a a b c
S:a b a a b c
↑
比较a和c,不相同,此时j=4,根据next[4]=1,将j移动到next[4]的位置,即j=1。
T:a b a a b a a b c a b a a b c
S:a b a a b c
↑
比较b和b,相同,j和i同时后移。
T:a b a a b a a b c a b a a b c
S:a b a a b c
↑
比较a和c,不相同,此时j=3,根据next[3]=1,将j移动到next[3]的位置,即j=1。
T:a b a a b a a b c a b a a b c
S:a b a a b c
↑
比较b和b,相同,j和i同时后移。
T:a b a a b a a b c a b a a b c
S:a b a a b c
↑
比较a和c,不相同,此时j=2,根据next[2]=0,将j移动到next[2]的位置,即j=0。
T:a b a a b a a b c a b a a b c
S:a b a a b c
↑
比较a和a,相同,j和i同时后移。
T:a b a a b a a b c a b a a b c
S:a b a a b c
↑
比较b和b,相同,j和i同时后移。
T:a b a a b a a b c a b a a b c
S:a b a a b c
↑
比较a和c,不相同,此时j=1,根据next[1]=0,将j移动到next[1]的位置,即j=0。
T:a b a a b a a b c a b a a b c
S:a b a a b c
↑
比较a和a,相同,j和i同时后移。
T:a b a a b a a b c a b a a b c
S:a b a a b c
↑
比较b和b,相同,j和i同时后移。
T:a b a a b a a b c a b a a b c
S:a b a a b c
↑
比较a和a,相同,j和i同时后移。
匹配成功!比较次数为9,选项A正确。