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<nLen;j++){if(needle.charAt(j)!=haystack.charAt(i+j))break;}if(j==nLen)return haystack.substring(i);}return null;}}

?

kmp： ?N(m+n)

http://www.youtube.com/watch?v=iZ93Unvxwtw

?

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<N && j<M; i++){j = dfa[pat.charAt(i)][j];}if (j == M) return i - M; //找到else return M;}}

?

轉載于:https://www.cnblogs.com/leetcode/p/4005042.html

總結

以上是生活随笔為你收集整理的strstr的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。