问题描述

输入两个字符串A、B，问在A中是否包含B，有几个？
例如：A="abcaabcabcab",B="abcab"
则有两处地方A包含B

问题分析

常规解决方法：暴力匹配，即把B串一位一位的与A串比较
if B[j]==A[i] i++ j++
if B[j]!=A[i] i=i-j+1, j=0 //i回溯，j置0
此时便会重复计算，因为回溯的时候，前面已经有了比较信息，能够确定哪些位是不需要比较的，所以KMP算法解决这个问题

KMP算法

两个概念：
前缀：从字符串首字开始，连续的位，但不包含全部
后缀：从字符串任何一位开始，不包含首位，直到末位
例如：abca
前缀有：a,ab,abc
后缀有：a,ca,bca

F数组

F[i]表示的是前i个字符组成字符串的最长相同的前缀后缀长度
KMP算法利用F数组跳过不需要重复比较的字符

具体过程分析参考
包括如何通过F数组，求解
如果求F数组
http://www.cnblogs.com/SYCstudio/p/7194315.html

心得

• 核心思想：利用前后缀相同，即利用B串字符中，可能出现重复顺序字符减少判别次数
• 求解F数组的时候：利用迭代分析法求

java代码

import java.util.Scanner;
public class Main {
    public static void main(String[]args){
        Scanner scanner=new Scanner(System.in);
        String AString=scanner.nextLine();
        String BString=scanner.nextLine();
        int n=AString.length();
        int m=BString.length();
        char[] A=AString.toCharArray();
        char[] B=BString.toCharArray();
        //求解F数组
        int[] F=new int[m];
        F[0]=-1;
        for (int i=1;i<m;i++){
            int j=F[i-1]; //指代i前面的字符串的最长相同前后缀的前缀最后一个字符的位置
            while ((B[j+1]!=B[i])&&(j>=0)){ //当B[i]不能连接到B[j]后面时,最长相同前后缀的长度不为0
                j=F[j]; //将j回溯，初始化
            }
            if (B[j+1]==B[i]) //如果能连接
                F[i]=j+1; //设置获取F[i]
            else F[i]=-1; //其他情况都不是，则设为-1
        }
        //利用F数组寻找匹配,输出匹配的开始位置
        int i=0;
        int j=0;
        while (i<n){
            if (A[i]==B[j]) {
                i++;
                j++;
                if (j == m) { //找到符合条件的
                    System.out.println(i-m+1); //输出开始位置
                    j=F[j-1]+1; //KMP算法，略过前缀与后缀相同的部分
                }
            }
            else {
                if (j==0) //如果没有任何可掠过的前缀和后缀相同的部分，B串直接往后移一个单位
                    i++;
                else j=F[j-1]+1; //同上
            }
        }
    }
}