For a given source string and a target string, you should output the first index(from 0) of target string in source string. If target does not exist in source, just return -1
Example:
If source = "source" and target = "target", return -1.
If source = "abcdabcdefg" and target = "bcd", return 1.
大致意思是给定两个字符串source和target，找出target串在source串中第一次出现的位置
解决这道题比较暴力的方式是用两层循环来遍历source和target，注意外层遍历source串的边界条件以及内层遍历target串时把循环变量j提出来，方便在循环外判断匹配结果。时间复杂度O(N * M)，代码如下：
class Solution {
public int strStr(String source, String target) {
if (source == null || source.length() == 0) {
return -1;
}
for (int i = 0; i < source.length() - target.length() + 1; i++) {
int j = 0;
while (j < target.length() && source.charAt(i + j) == target.charAt(j)) {
j++;
}
if (j == target.length()) {
return i;
}
}
return -1;
}
}
暴力求解的时间复杂度这么高，是因为每次遍历到一个字符串时，检查工作相当于从无开始，之前的遍历检查不能优化当前的遍历检查。著名的KMP算法就是通过利用匹配失败后的信息，尽量减少target与source的匹配次数以达到快速匹配的目的。
KMP算法是一种改进的字符串匹算法，由D.E.Knuth，J.H.Morris和V.R.Pratt于1977年联合发明。该算法预先为target构造了一个next数组，时间复杂度O(M)，next[i]的含义是：在target[i]之前的字符串target[0...i-1]中，必须以target[i-1]结尾的后缀子串（不能包含target[0]）与必须以target[0]开头的前缀子串（不能包含target[i-1]）最大匹配长度是多少。
假设从source[i]字符出发时，匹配到source[j]字符发现与target中的字符不一致。也就是说，source[i...j-1]与target[0...j-i-1]一样，直到发现source[j] != target[j-i]，匹配失败。下一次的匹配检查不再像普通解法那样回退到source[i+1]重新开始与target[0]的匹配过程，而是直接让source[j]与target[k]进行匹配检查，k为next[j-i]定位的target中最长匹配前缀的下一个位置。
使用KMP算法，source中匹配的指针不必回退与target初始位置重新匹配，并使target沿着source向右滑动，所以匹配过程的时间复杂度O(N)。
总的时间复杂度O(N + M)，代码如下：
public class KMPAlgorithm {
/**
* 由target构造next数组，时间复杂度O(M)
*
* @param target
* @return
*/
public static int[] getNextArray(String target) {
int len = target.length();
if (len == 1) {
return new int[]{-1};
}
int[] next = new int[len];
next[0] = -1;
next[1] = 0;
int i = 2;
int cn = 0; // 向前跳的位置，初始时置0
while (i < len) {
if (target.charAt(i - 1) == target.charAt(cn)) {
next[i++] = ++cn;
} else if (cn > 0) { // 不等，继续往前跳
cn = next[cn];
} else {
next[i++] = 0;
}
}
return next;
}
/**
* KMP的匹配过程，source指针不回退，target沿着source向右滑动，时间复杂度O(N)
*
* @param source
* @param target
* @return
*/
public static int getIndexOf(String source, String target) {
if (source == null || target == null || target.length() < 1 || source.length() < target.length()) {
return -1;
}
int n = source.length();
int m = target.length();
int i = 0;
int j = 0;
int[] next = getNextArray(target);
while (i < n && j < m) {
if (source.charAt(i) == target.charAt(j)) {
i++;
j++;
} else if (next[j] == -1) {
i++;
} else {
j = next[j];
}
}
return j == m ? i - j : -1;
}
public static void main(String[] args) {
String str = "abcabcababaccc";
String match = "ababa";
System.out.println(getIndexOf(str, match));
}
}
参考资料：《程序员代码面试指南：IT名企算法与数据结构题目最优解》 P492
