2. 字符串查找

KMP算法：KMP算法的关键是利用匹配失败后的信息，尽量减少模式串与主串的匹配次数以达到快速匹配的目的。具体实现就是实现一个next（）函数，函数本身包含了模式串的局部匹配信息。时间复杂度O（m+n）。

通过getNext()实现部分匹配值，然后利用KMP算法计算是否匹配。

代码如下：

package LintCode;


public class Solution {
/*
* @param source: source string to be scanned.
* 
* @param target: target string containing the sequence of characters to
* match
* 
* @return: a index to the first occurrence of target in source, or -1 if
* target is not part of source.
*/


public static int strStr(String source, String target) {
// write your code here
if (source == null || target == null)
return -1;
if(source == "" && target == "")
return 0;
if(source == "")
return -1;
if(target == "")
   return 0;
if(source.equals(target))
return 0;
int lengthP = target.length();
int[] a = getNext(lengthP, target);
int pos = kmp(0, a, source, target);
return pos;
}


public static int[] getNext(int lengthP, String target) {// lengthP为模式串P的长度
int[] next = new int[lengthP];
for (int i = 0; i < lengthP; i++) {
next[i] = 0;
}
String a, b;
int j = 0, k = -1;// j为P串的下标，k用来记录该下标对应的next数组的值
next[0] = -1;// 初始化0下标下的next数组值为-1
while (j < lengthP) { // 对模式串进行扫描
a = target.substring(j, j + 1);
if (k == -1) {
j++;
k++;
if (j == lengthP)
break;
next[j] = k;// 设置next数组j下标的值为k
} else if (k != -1 && a.equals(target.substring(k, k + 1))) {// 串后缀0与前缀没有相等的子串或者此时j下标下的字符与k下的字符相等。
j++;
k++;
if (j == lengthP)
break;
next[j] = k;// 设置next数组j下标的值为k
} else
k = next[k];// 缩小子串的范围继续比较
}
return next;
}


public static int kmp(int k, int next[], String source, String target) {
System.out.print("next[i]:"); // 3
for (int i = 0; i < target.length(); i++) {
System.out.print(next[i]);
}
System.out.println("");
String a, b;
int posP = 0, posT = k;// posP和posT分别是模式串pat和目标串T的下标，先初始化它们的起始位置
int lengthP = target.length();// lengthP是模式串pat长
int lengthT = source.length();// lengthT是目标串T长
a = target.substring(posP, posP + 1);
   b = source.substring(posT, posT + 1);
while (posP < lengthP && posT < lengthT) {// 对两串扫描
if(posP != -1)
{
a = target.substring(posP, posP + 1);
   b = source.substring(posT, posT + 1);
}
System.out.println("a:" + a + " b:" + b + " posP" + posP + " posT" + posT);
if (posP == -1|| a.equals(b)) {// 对应字符匹配
posP++;
posT++; 
} else
posP = next[posP];// 失配时，用next数组值选择下一次匹配的位置
}
if (posP < lengthP)
return -1;
else {
System.out.println("posP:" + posP + " posT" + posT);
return posT-lengthP;// 匹配成功
}
}


public static void main(String[] args) {
// TODO 自动生成的方法存根
String source, target;
source = "tartarget";  //可随意更换字符串内容
target = "target";        //可随意更换字符串内容
int a = strStr(source, target); 
System.out.println(a);
}
}