[理学]北京信息科技大学数据机构课件第4章.ppt

例：主串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 2. 简单的模式匹配算法 一、简单匹配算法 例：主串S=ababcabcacbab，模式T=abcac a b a b c a b c a c b a b a b c a c i=4，j=1失败 i回溯到5，j回溯到1 第 4 趟 i j 2. 简单的模式匹配算法 一、简单匹配算法 例：主串S=ababcabcacbab，模式T=abcac a b a b c a b c a c b a b a b c a c i=4，j=1失败 i回溯到5，j回溯到1 第 4 趟 i j 2. 简单的模式匹配算法 一、简单匹配算法 例：主串S=ababcabcacbab，模式T=abcac a b a b c a b c a c b a b a b c a c i=5，j=1失败 i回溯到6，j回溯到1 第 5 趟 i j 2. 简单的模式匹配算法 一、简单匹配算法 例：主串S=ababcabcacbab，模式T=abcac a b a b c a b c a c b a b a b c a c i=5，j=1失败 i回溯到6，j回溯到1 第 5 趟 i j 2. 简单的模式匹配算法 一、简单匹配算法 例：主串S=ababcabcacbab，模式T=abcac a b a b c a b c a c b a b a b c a c i=11，j=6，T中全部字符都比较完毕，匹配成功。 第 6 趟 i j i j i j i j i j 2. 简单的模式匹配算法 一、简单匹配算法 1. 在串S和串T中设比较的起始下标i和j； 2. 循环直到S或T的所有字符均比较完； 2.1 如果S[i]=T[j]，继续比较S和T的下一个字符； 2.2 否则，将i和j回溯，准备下一趟比较； 3. 如果T中所有字符均比较完，则匹配成功，返回匹配的起始比较下标；否则，匹配失败，返回0； 2. 简单的模式匹配算法 一、简单匹配算法 int Index(SString S, SString T, int pos) { // 返回子串T在主串S中第pos个字符之后的位置。若不 // 存在， 则函数值为0。 // 其中，T非空，1≤pos≤StrLength(S)。 i = pos; j = 1; while (i = S[0] j = T[0]) { if (S[i] == T[j]) { ++i; ++j; } // 继续比较后继字符 else { i = i-j+2; j = 1; } // 指针后退重新开始匹配 } if (j T[0]) return i-T[0]; else return 0; } // Index 一、简单匹配算法 先比较模式串的第一个字符， 再比较模式串的最后一个字符， 最后比较模式串中从第二个到 第n-1个字符。 二、首尾匹配算法 int Index_FL(SString S, SString T, int pos) { sLength = S[0]; tLength = T[0]; i = pos; patStartChar = T[1]; patEndChar = T[tLength]; while (i = sLength – tLength + 1) { if (S[i] != patStartChar) ++i; //重新查找匹配起始点 else if (S[i+tLength-1] != patEndChar) ++i; // 模式串的“尾字符”不匹配 else {