数据结构:BM算法

设计思路

BM 算法是一种后缀匹配算法,其具有比 KMP 算法更优秀的性能表现.其核心思想有二
,第一是坏字符,坏字符就是 pattern 与 text 从右往左第一失配的在 text 中的字符,
二是好后缀,好后缀就是 pattern 与 text 从右往左连续匹配成功的子串.对于坏字符
和好后缀,有各自的模式串移动规则,可以确定各自失配时需要移动的位数,最终选
择二者中移动位数较大者移动.在主函数中,让用户输入文档名与需要查找的单词.
每次从文档中读取一行进行匹配搜索,每次使用 BM 算法搜索完成后,若搜索到单词,
则将主串中开始匹配的位置定为查找到单词的下一行,使用 BM 算法进行下一个匹配
搜索,直至搜索完当前行.而后循环直至匹配完整个文档.

阅读更多

数据结构:迷宫问题

设计思路

图编号

如图所示,从上到下,从左到右,给 17 个顶点进行编号,以两个顶点代表一条边,例入 2-3 代表可以从顶点 2 走到顶点 3。问题即为求解从 2 -> 17 的通路。

阅读更多