字符串基础与模式匹配

字符串如何比较大小？

• 规则: 逐字符比较字符编码值;
• 编码: ASCII 或 Unicode;
• 结果: 首个不同的字符决定大小, 全部相同则长度决定;

字符串有哪些存储结构？

• 顺序存储: 用数组存放字符, 支持按下标随机访问;
• 链式存储: 用链表挂接字符, 插入删除灵活但访问需要遍历;
• 选型: 需要频繁按下标访问时用顺序存储;

什么是模式匹配？

• 输入: 文本串 T 和模式串 P;
• 任务: 在 T 中寻找 P 出现的位置;
• 单模式匹配: 给定一个文本串和一个特定模式串, 寻找模式串的所有出现位置;
• 多模式匹配: 给定一个文本串和一组模式串, 寻找所有模式串的所有出现位置;
• 多模式的简单做法: 对每个模式串各运行一次单模式匹配算法;

模式匹配有哪些搜索策略？

• 基于前缀搜索: 在搜索窗口中正向搜索, 寻找最长公共前缀;
• 基于后缀搜索: 在搜索窗口中反向搜索, 寻找最长公共后缀;
• 基于子串搜索: 以模式串中的某个子串为比较入口;
• 适用范围: 三种策略同样适用于多模式匹配;