串（String）
串是由有限个字符组成的一种线性结构，其中每个字符都来自某个字符表（Alphabet）Σ，比如 ASCII 字符集或 Unicode 字符集。
串 ADT 的主要操作可以归纳为如下：
| 操作方法 | 功能描述 |
|---|---|
| length( ) | 查询串的长度 输入：无 输出：非负整数 |
| charAt(i) | 返回第 i 个字符 输入：一个非负整数 输出：一个字符 |
| substr(i, k) | 返回从第 i 个字符起、长度为 k 的子串 输入：两个非负整数 输出：一个字符串 |
| prefix(k) | 返回长度为 k 的前缀 输入：一个非负整数 输出：一个字符串 |
| suffix(k) | 返回长度为 k 的后缀 输入：一个非负整数 输出：一个字符串 |
| equals(T) | 判断 T 是否与当前字符串相等 输入：一个字符串 输出：布尔标志 |
| concat(T) | 将 T 串接在当前字符串之后 输入：一个字符串 输出：一个字符串 |
| indexOf(P) | 若 P 是当前字符串的一个子串，则返回该子串的起始位置；否则返回 -1 输入：一个字符串 输出：非负整数 |
串具有两个突出的特点：结构简单，规模庞大。
-
结构简单，一方面是线性结构，另一方面是指字符表规模不大，在某些应用问题中，字符表的规模甚至可能极小。以生物信息序列为例，组成蛋白质（文本）的氨基酸（字符）只有约 20 种，而组成DNA序列（文本）的碱基（字符）则只有 4 种。
-
然而，这类文本的规模往往很大，其中每个字符都大量重复地出现，串中字符的重复率一般非常高。
** 这里我们将直接采用Java本身提供的String类。 **
串模式匹配（String pattern matching）
在串文本的众多应用问题中，会反复涉及到一项非常基本的判断性操作：
给定串 T（称作主串）和串 P（称作模式串），T 中是否存在的某个子串与 P 相同？如果存在，找到该子串在 T 中的起始位置。
实际上，根据具体应用的不同，串匹配问题有多种形式：
-
有些场合属于串匹配检测（Pattern detection）问题：我们只关心是否存在匹配，而不关心具体的匹配位置。
-
有些场合则属于定位（Pattern location）问题：若经判断的确存在匹配，则还需要确定具体的匹配位置。
-
有些场合属于计数（Pattern counting）问题：倘若有多处匹配，统计出这些匹配子串的总数。
-
有些场合则属于枚举（Pattern enumeration）问题：在有多处匹配时，报告出所有匹配的具体位置。
比如，以上邮件过滤器的例子就属于检测型问题：一旦特征匹配，即可判定为垃圾邮件，从而直接删除，或者将其隔离以待用户确认，此时我们并不关心特征串的具体位置。然而，反病毒系统的任务则属于枚举型问题：不仅必须在二进制代码中找出所有的病毒特征串，还需要报告它们的具体位置，以便修复。
蛮力算法
蛮力串匹配算法是最直接、直观的方法。
我们想象着将主串和模式串分别写在两条印有等间距方格的纸带上，主串对应的纸带固定，模式串的首字符与主串的首字符对齐，沿水平方向放好。主串的前m个字符将与模式串的m个字符两两对齐。
接下来，自左向右检查对齐的每一对字符：如果匹配，则转向下一对字符；如果失配，则说明在这个位置主串与模式串无法匹配，于是将模式串对应的纸带右移一个字符，然后从首字符开始重新对比。
若经过检查，当前的m个字符对都是匹配的，则匹配成功，并返回匹配子串的位置。
蛮力算法的具体实现：
package other;
public class PM_BruteForce {
/*
* 串模式匹配：蛮力算法 若返回位置i > length(T) - length(P)，则说明失配 否则，i为匹配位置
*/
//////////////////////////////////////////////////////////////////////////
// T: 0 1 . . . i i+1 . . . i+j . . n-1
// --------------------|-------------------|------------
// P: 0 1 . . . j . .
// |-------------------|
//////////////////////////////////////////////////////////////////////////
public static int PM(String T, String P) {
int i;// 模式串相对于主串的起始位置
int j;// 模式串当前字符的地址
for (i = 0; i <= T.length() - P.length(); i++) {// 主串从第i个字符起，与
for (j = 0; j < P.length(); j++) {// 模式串的当前字符逐次比较
if (T.charAt(i + j) != P.charAt(j))
break;// 若失配，模式串右移一个字符
}
if (j >= P.length())
break;// 找到匹配子串
}
return (i);
}
}
在最坏情况下蛮力算法的运行时间为主串、模式串长度的乘积，因此只适用于小规模的串匹配应用。
网友评论