第 9 页Java 库中的实现内容indexOf()方法返回给定字符串第一次出现的索引。Java 代码演示抓取雅虎股票价格。javaString name http://finance.yahoo.com/q?s; In in new In(name args[0]); String text in.readAll(); int start text.indexOf(Last Trade:, 0); int from text.indexOf(b, start); int to text.indexOf(/b, from); String price text.substring(from 3, to);底部输出结果goog返回582.93msft返回24.84。物理含义text.readAll()把整个网页的字符数据全部加载到内存中的text字符串里。第一个indexOf从索引 0 开始找返回Last Trade:的下标。第二个indexOf从start开始往后找b。第三个indexOf从from开始往后找/b。substring(from 3, to)提取出价格字符串。底层的物理事实Java 的indexOf方法内部使用的是暴力搜索算法。对于绝大多数日常小规模文本它的速度是可以接受的。但如果文本极度庞大或者模式具有大量重复前缀暴力搜索就会面临性能瓶颈。这就是接下来要改进算法的原因。第 12 页暴力算法的物理动作内容“Check for pattern starting at each text position.”在文本的每个位置检查模式。图示文本A B A C A D A B R A C模式A B R A。标注了三个变量i文本中的起始位置、j模式中的当前比较位置、ij文本中当前比较的确切位置。红色字符表示发生不匹配mismatch灰色表示在发生不匹配后后续不需要再比较的字符。物理含义i是文本指针偏移量表示当前假设模式匹配的起点。j是模式指针表示当前正在比较模式中的第几个字符。物理动作把模式对齐到文本的i位置。然后j从 0 开始递增比较txt.charAt(ij)和pat.charAt(j)。如果字符相同j继续增加如果字符不同图中红字说明从i开始的匹配失败。失败后i增加 1模式整体向右滑动一格j重置为 0重新开始比较。如图中i0比较到ij2时C和R不匹配然后i变成 1继续尝试。第 13 页暴力算法的 Java 实现内容javapublic static int search(String pat, String txt) { int M pat.length(); int N txt.length(); for (int i 0; i N - M; i) { int j; for (j 0; j M; j) if (txt.charAt(ij) ! pat.charAt(j)) break; if (j M) return i; } return N; }右下角标注“index in text where pattern starts”返回匹配的起始索引以及“not found”未找到返回 N。物理含义外层循环i从 0 遍历到N-M。N-M是模式能放进文本的最大起始偏移。内层循环j遍历模式的所有字符。每次比较文本的ij和模式的j。如果遇到不匹配break跳出内层循环。跳出后检查j M。如果成立说明内层循环完整走完找到了匹配返回i。如果外层循环结束还没找到返回N表示未找到。物理内存每次比较是读取txt数组的ij槽位和pat数组的j槽位。不匹配时i加一j归零文本指针发生回退。第 14 页暴力算法的最坏情况内容“Brute-force algorithm can be slow if text and pattern are repetitive.”如果文本和模式具有重复性暴力算法会很慢。图示文本A A A A A A A A A B模式A A A A B。最坏情况“~ M N char compares.”约 M*N 次字符比较。物理含义文本是极长的A序列最后跟着一个B。模式是较短的A序列最后跟着一个B。每次i增加 1内层j都会匹配到模式的最后一个字符B才发生不匹配。每次失败i只前进了 1然后重新比较了M-1个A。前面的A被反复比较这是纯粹的浪费。极端的物理后果如果 N 是几百万M 是几万M*N 是百亿次操作程序会卡死。第 15 页流处理中不能回退内容“In many applications, we want to avoid backup in text stream.”在很多应用中我们希望避免在文本流中回退。模型将输入视为数据流标准输入。图示暴力算法遇到不匹配时需要“backup”回退。“Approach 1. Maintain buffer of last M characters.”方法 1维护最近 M 个字符的缓冲区。“Approach 2. Stay tuned.”方法 2后续介绍。物理含义在网络、传感器等场景中数据流是单向的。一旦从流中读取了字符就无法让指针回退去重新读取。暴力算法中i每次只增加 1但j的比较已经消耗了文本指针要重新对齐就需要回溯文本。方法 1 的物理代价为了允许回退必须分配一个大小为 M 的缓冲区buffer把最近的 M 个字符存起来。这会占用内存。第 16 页显式回退的实现内容“Same sequence of char compares as previous implementation.”与之前的实现具有相同的字符比较序列。i指向文本中已经匹配的字符序列的末尾。j存储已经匹配的字符数。代码javafor (i 0, j 0; i N j M; i) { if (txt.charAt(i) pat.charAt(j)) j; else { i - j; j 0; } // explicit backup } if (j M) return i - M; else return N;箭头标注“explicit backup”显式回退。物理含义这个版本的代码逻辑不同但比较次数一样。i一直往前走j记录匹配了多少个。遇到不匹配执行i - j; j 0;。物理动作是文本指针i回退j个位置。因为刚才比较了j个字符i已经越过了起点j个位置。这明确暴露了暴力算法在物理上的致命弱点文本指针必须向后退i - j。第 17 页算法挑战内容“Brute-force is not always good enough.”暴力算法并不总是足够好。理论挑战Theoretical challenge线性时间保证Linear-time guarantee。标注这是基础算法问题。实际挑战Practical challenge避免文本流中的回退Avoid backup in text stream。标注通常没有空间或时间保存文本。底部展示了一大段重复的文本Now is the time...其中隐藏着attack at dawn。物理含义理论挑战要求在 O(NM) 时间内完成搜索保证最坏情况下也能快速返回。实际挑战要求算法不依赖i - j这种回退动作因为数据流可能已经流走无法回退。这为接下来的 KMP 算法Knuth-Morris-Pratt指明了设计目标利用模式自身的结构信息在不回退文本指针的情况下实现线性时间搜索。