KMP

主串中查找子串，返回开始的位置

package wg.interview;
import java.util.Scanner;
// 返回子串在主串中第pos开始的位置
public class KMP {
        public static int getNext(String longStr, String shortStr){
            char[] main = longStr.toCharArray();
            char[] son = shortStr.toCharArray();
            int i = 0; // 主串当前位置下标处
            int j = 0; // 子串中当前位置下标值，子串从第一个开始
            while (i < main.length && j<son.length){
                if (main[i] == son[j]){
                    i++;
                    j++;
                }else {
                    i = i-j+1; // 主串位置往后移动一位
                    j = 0; // 子串继续回到起点
                }
            }
            if (j == son.length){
                return i-j;
            }else {
                return -1;
            }
        }
        public static void main(String[] args) {
            String shortStr = "abc";
            String longStr = "qqqabcdf";
            System.out.println("Found at: " + KMP.getNext(longStr,shortStr));
        }
}