判断字符串中是否包含有某子字符（串），是各种字符串相关算法题的基础，这里列举了博主学习时写的一些方法。如果包含某SubString，我们返回它在字符串的位置，如果不包含，返回-1。
1. 朴素算法
public static int matchSubString(String str, String sub) {
char[] strList = str.toCharArray();
char[] subList = sub.toCharArray();
int subLen = sub.length();
int strLen = str.length();
for(int i = 0; i <= strLen - subLen; i++) {
int temp = i;
int j = 0;
while(j < subLen && strList[temp] == subList[j]) {
j++;
temp++;
}
if (j == subLen) {
return i;
}
}
return -1;
}
2. String.indexOf() 方法
public static int matchSubString(String str, String sub) {
return str.indexOf(sub);
}
3. KMP算法
Donald Knuth 和 Vaughan Pratt 于1970年提出了线性复杂度的字符串匹配方法，James Morris在同年也独立发现了相同的方法，他们三人于1977年一起发布了相关论文，以他们三人姓氏命名的Knuth–Morris–Pratt(KMP)算法由此诞生。简单来说，与朴素算法最大的不同是，KMP算法不会去重复查找主字符串中已匹配过的字符，因此，KMP算法将朴素算法的O(m*n)优化成了O(m+n)。
朴素算法的思路是，如果本次迭代未匹配到，下次迭代把pattern后移一位，然后再次尝试匹配。而KMP算法运用了部分匹配表（Partial Match Table）来优化这个过程，这也是KMP算法的核心。我们用一个例子来说明，我们有如下两个字符串，主字符串和待匹配字符串pattern：
主String：
Pattern：想要求出Pattern的PMT，首先我们要明白前缀和后缀的概念，比如我们有一个字符串 ababa, 那么它的前缀有{a,ab,aba,abab}，它的后缀有{a,ba,aba,baba}，那么，字符串的最长公共前后缀就是aba，长度为3，这就是我们要在PMT里填入的值。Pattern可以被看做不同长度的字符串，比如我们说到的ababa，就是Pattern的前5位，那么在PMT的第五位就赋值为3，也就是PMT[4] = 3。同理，完整的PMT表就是：| a | 0 | | | | | |
| ab | | 0 | | | | |
| aba | | | 1 | | | |
| abab | | | | 2 | | |
| ababa | | | | | 3 | |
| ababac | | | | | | 0 |
换种写法：1| index | 0 | 1 | 2 | 3 | 4 | 5 |
| PMT | 0 | 0 | 1 | 2 | 3 | 0 |
| Next | -1 | 0 | 0 | 1 | 2 | 3 |
为了方便使用，我们将PMT的值，整体后移一位，然后将空出来的第一位补上-1，记作Next行。个人认为这么做纯粹是为了编程简洁，在后面代码中会进一步说明。### Iteration 1：第一次迭代，Pattern的第四位匹配失败，朴素算法在此时会将Pattern后移一位。而KMP算法，就要查询Next数组中对应的值了，此次迭代，Pattern的第四位，也就是Pattern[3]匹配失败，那么我们便查询Next[3]对应的值，对应的值是1，那么，就将Pattern[1]的位置对齐到当前匹配失败的位置。### Iteration 2：第二次迭代，我们不用管Pattern[1]之前的字符了，因为根据部分匹配表，之前的字符已经是相同的了。然后Pattern[1]匹配失败，这里Next[1]对应的值是0，于是将Pattern[0]对齐当前匹配失败的位置。### Iteration 3：第三次迭代，Patttern[0]匹配失败，Next[0]对应的-1, 所以将Pattern后移一位。这时就可以看出，实际上在Next表中添加的-1仅仅是为了后移一位，你完全可以设它为-100，只要在代码中你能判断出，当前是要整体后移一位就可以，只不过，使用-1可以使你的代码更简洁。### Iteration 4：第四次迭代，匹配到弟6位失败，Next[5]对应的是3，于是将Pattern[3]与当前匹配失败的位置对齐。### Iteration 5:第五次迭代，只需要看Pattern[3]、Pattern[4]和Pattern[5]是否匹配，结果是匹配，于是匹配完成。### 代码：我们可以先得出PMT，然后后移一位得出Next表。`Java public static int[] PMT(String str) { int[] pmt = new int[str.length()]; pmt[0] = 0; int i = 0; int j = 1; int count = 0; while(j < str.length()) { if(str.charAt(i) == str.charAt(j)) { count++; pmt[j] = count; i++; j++; } else { count = 0; pmt[j] = 0; i = 0; j++; } } return pmt; } public static int[] getNext(String str) { int[] pmt = PMT(str); int[] next = new int[str.length()]; next[0] = -1; for (int i=0;i < str.length()-1; i++) { next[i+1] = pmt[i]; } return next; }`当然我们也可以不写PMT表，我们直接得出Next表，这样会更加简洁：`java public static int[] getNext(String str) { int[] next = new int[str.length()]; next[0] = -1; int i = 0; int j = 1; int count = 0; while(j<str.length()-1) { if(str.charAt(i) == str.charAt(j)) { count++; next[j+1] = count; i++; j++; } else { count = 0; next[j+1] = count; i = 0; j++; } } return next; }`我们的主循环就是：`java public static int matchSubString(String str, String sub) { char[] strList = str.toCharArray(); char[] subList = sub.toCharArray(); int[] next = getNext(sub); int subLen = sub.length(); int strLen = str.length(); int i = 0,j = 0; while(i<strLen && j<subLen ) {// 这里就是设-1的好处，因为我们不用单独为了它写一种情况，比如：// if (j == -100) {// i++;// j = 0;// } if (j == -1 || strList[i] == subList[j]) { i++; j++; } else{ j = next[j]; } //匹配到字符串 if(j == subLen) { return i - subLen; } } //未匹配到 return -1; }`## 3. 结果input:> str: Some Computing Science students are studying in the Computing Science Center. > sub: Computingoutput:> 5很显然，这几种方法都是返回最先找到的SubString位置，后面若有相同的SubString会被忽略掉。