一、引言
在文本编辑中，经常遇到要在一段文本中找出一个字符串的全部出现位置的情况，这就需要用到字符串匹配算法，典型的情况是，给定一段正在编辑的文本，用户提供一个特定的单词，然后程序需要找出这个单词在文本中的出现位置。用户给定的单词或字符串被称为模式，因此字符串匹配又被称为模式匹配。
二、问题描述
假设文本是一个长度为n的字符数组T[1,2,...,n]，模式是一个长度为m <= n的数组P[1,2,...,m]，如果有0 <= s <= n - m使得T[s+1, s+2, ... , s+m] = P[1, 2, ..., m]，则s就被称为一个有效位移，那么字符串匹配的目的就是从文本字符串中找出所有的有效位移s。
如图-1所示，图中的文本字符串T=abcabaabaabcabac，模式P=abaa，该模式在文本中进出现了一次，在位移s=3处，因此位移s=3就是有效位移。
图-1 字符串匹配
三、朴素的字符串匹配算法
3.1 算法分析
所谓的朴素字符串匹配算法是最简单最直接的的字符串匹配算法，它从对文本中0到n-m+1的每一个位移s都进行一次P[1,2,...,m] = T[s+1.s+2,...,s+m]的检测，算法伪代码如下所示：
如图-2所示，朴素的字符串匹配可以看作是一个包含着模式的模版沿文本的滑动，并对每个位移检查模版上的字符是否与文本上的相应字符相等。 伪代码中第三行开始的for循环显示地对每一个位移进行考察是否为有效位移，第四行代码测试当前位移是否有效，该行隐含着一层循环，该循环逐字符地检查文本与模式是否匹配。在朴素字符串匹配算法中，需要检查为位移个数为n-m+1，检查每个位移时需要比较的字符个数为m，所以朴素字符串匹配算法的时间复杂度为O((n-m+1)*m)，但是由于不需要额外的存储空间，该算法的空间复杂度为O(1)。
图-2 朴素字符串匹配
3.2 代码实现
匹配算法：
package string_match;
import java.util.ArrayList;
public class NativeMatch {
public int[] match(String pattern, String txt, ArrayList<Character> alphabet) {
// 检查字输入符串是否为空
if (pattern == null || txt == null) {
System.out.println("Input can't be null!");
return null;
}// if
// 检查输入字符串是否为空字符串
int pLen = pattern.length();
int tLen = txt.length();
if (pLen == 0x00 || tLen == 0x00){
System.out.println("Input can't be empty string!");
return null;
}// if
// 字符串匹配
ArrayList<Integer> shift = new ArrayList<>(); // 用于存放匹配结果
for (int i = 0; i <= tLen - pLen; i++) { // 依次检查每一个位移
boolean flag = true;
for (int j = 0; j < pLen; j++) { // 对当前位移进行匹配检查
flag = true;
if (pattern.charAt(j) != txt.charAt(i+j)) {
flag = false;
break;
}// if
}// for
if (flag == true)
shift.add(i);
}// for
// 转换匹配结果
int matchNum = shift.size();
int[] result;
if (matchNum == 0x00) {
result = new int[1];
result[0] = -1;
}else {
result = new int[matchNum];
for (int i = 0; i < matchNum; i++)
result[i] = shift.get(i);
}// if
return result;
}// match
}/*NativeMatch*/
测试样例与测试程序：
package string_match;
import java.util.ArrayList;
public class MatchTest {
public static void main(String[] args) {
String str1 = "";
String str2 = "Chongqing University is in Chongqing";
String str3 = "Chongqing";
String str4 = " ";
String str5 = "Beijing";
String str6 = null;
String str7 = "aaaaaaaaa";
matchTest(str6, str6, alphabet);
System.out.println();
matchTest(str1, str2, alphabet);
System.out.println();
matchTest(str2, str3, alphabet);
System.out.println();
matchTest(str3, str2, alphabet);
System.out.println();
matchTest(str4, str2, alphabet);
System.out.println();
matchTest(str5, str2, alphabet);
System.out.println();
matchTest("aaa", str7, alphabet);
}// main
public static void matchTest(String pattern, String txt) {
StringMatcher matcher = new NativeMatch();
System.out.println("text: " + txt);
System.out.println("pattern: " + pattern);
int[] matchShift = matcher.match(pattern, txt);
if (matchShift != null) {
if (matchShift[0] != -1) {
System.out.print("Pattern matches at shift of: ");
for (int shift : matchShift)
System.out.print(shift + " ");
System.out.println();
} else {
System.out.println("No match found!");
}// if
}// if
}// matchTest
}/*MatchTest*/
运行结果：
四、总结
不难发现，朴素的字符串匹配算法虽然简单，但是并不是最优的匹配算法，因为每检查一个新的位移时，都需要回过头来重新从模式的第一个字符开始检查，在模式字符串和文本字符串中许多字符被重复匹配了多次，这无疑增加了不必要的时间消耗。在接下来的两篇博文中，我们将介绍两种匹配时间复杂度为O(n)的匹配算法，他们通过预处理的方法较好的解决了这个问题。
需要说明的是，虽然朴素字符串匹配算法并不是最优解，但是在文本字符串长度不大的前提下，朴素字符串匹配算法依然可以取得不错的表现，因此该算法并没有被完全淘汰，而是依然有着较为广泛的应用。