第4章-串PPT.pptVIP

求子串 操作步骤： Step 1：如果串空或起始位置与子串长度不合理，不能 取。否则，转Step 2； Step 2：设置一工作串temp，按子串长，申请串空间； Step 3：把主串从index起的length个字符复制给工作串 temp； Step 4：工作串复制给子串； Step 5：销毁工作串。 串插入 操作步骤： Step 1：若i值不在插入范围，不能插入；否则Step2； Step 2：从S中取子串“s1s2…si-1”，暂存于工作串 temp； Step 3：将T连接到串temp后； Step 4：将temp串与S的子串“si…sn”相联； Step 5：将temp赋给S； Step 6：销毁temp。 串删除 操作步骤： Step 1 ：删除位置或删除长度不合理，不能删除，否 则，转Step 2； Step 2 ：从起始位置开始到最后的字符个数不足len 个，只需修改串长； 否则，转Step 3； Step 3 ：分别从主串中取子串“s1s2…si-1”和 “si+len…sn”，并把两个子串连结赋给工作 串temp； Step 4：把工作串temp复制给主串，并销毁工作串。 4.4 模式匹配 BF算法 1 KMP算法 2 模式匹配 设S和T是两个给定的串，在串S中找等于T的子串的过程称为模式匹配(pattern matching)。其中，S称为主串，T称为模式(pattern)。如果找到，称为匹配成功，否则称为匹配失败。 BF算法示意图 Play si …… 主串S 模式T tj j i … 回溯 i 回溯 j 模式匹配——BF算法 si …… 主串S 模式T j i … tj 模式匹配——BF算法 si …… 主串S 模式T j i … tj 模式匹配——BF算法 例：主串S=ababcabcacbab，模式T=abcac a b a b c a b c a c b a b i=3，j=3失败； i回溯到2，j回溯到1 i j i j i j 第 1 趟 a b c a c 模式匹配——BF算法 例：主串S=ababcabcacbab，模式T=abcac a b a b c a b c a c b a b i=3，j=3失败； i回溯到2，j回溯到1 j i 第 1 趟 a b c a c 模式匹配——BF算法 例：主串S=ababcabcacbab，模式T=abcac a b a b c a b c a c b a b i=2，j=1失败 i回溯到3，j回溯到1 第 2 趟 i j a b c a c 模式匹配——BF算法 例：主串S=ababcabcacbab，模式T=abcac a b a b c a b c a c b a b i=2，j=1失败 i回溯到3，j回溯到1 第 2 趟 i j a b c a c 模式匹配——BF算法 例：主串S=ababcabcacbab，模式T=abcac a b a b c a b c a c b a b a b c a c i=7，j=5失败 i回溯到4，j回溯到1 第 3 趟 i j i j i j i j i j 模式匹配——BF算法 例：主串S=ababcabcacbab，模式T=abcac a b a b c a b c a c b a b a b c a c i=7，j=5失败 i回溯到4，j回溯到1 第 3 趟 i j 模式匹配——BF算法 例：主串S=ababcabcacbab，模式T=abcac a b a b c a b