N(n*m)的时间复杂度

public class Solution {public String strStr(String haystack, String needle) {     int nLen = needle.length();    int hLen = haystack.length();        if(nLen==hLen && nLen==0)        return "";    if(nLen == 0)        return haystack;    for(int i=0; i<= hLen-nLen; i++){        int j = 0;        for( ; j

 

kmp：  N(m+n)

 

constructs dfa[][] in time and space to RM.  R is the set of charactor occur. 

 

 

 

package com.kmp; public class KMP {     private String pat;    private int[][] dfa; //二维字典         public KMP(String pat){        this.pat = pat;        int M = pat.length();        int R = 256;        //二维字典的构造        dfa = new int[R][M];        dfa[pat.charAt(0)][0] = 1;        for (int X = 0, j = 1; j< M; j++){            //复制前面某一列的所以跳转，至当前列，这某一列可视为参照列            for( int c = 0; c < R; c++) dfa[c][j] = dfa[c][X];            dfa[pat.charAt(j)][j] = j + 1; //第j个字节，刚好在第j个位置上，说明匹配成功            X = dfa[pat.charAt(j)][X]; //更新参照列的位置        }    }         public int find(String content){        // 查找逻辑，类似游戏        int i, j;        int N = content.length();        int M = pat.length();        for (i = 0, j = 0; i