Q：Returns the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.
A： 本题追求代码简单省额外空间则用nested loop； 追去快则用KMP以及其他基于FSA的方法，但是需要额外空间。
public class Solution {
public int strStr(String haystack, String needle) {
if (haystack == null || needle == null || haystack.length() < needle.length()) return -1;
int res = -1;
int m = haystack.length();
int n = needle.length();
for(int j = 0 ; j <= m - n; j ++){
int i;
for(i = 0; i < n; i++){
if (needle.charAt(i) != haystack.charAt(i+j)) break;
}
if (i == n ){
res = j;
break;
}
}
return res;
}
}
方法1: python version 1
class Solution(object):
def strStr(self, haystack, needle):
"""
:type haystack: str
:type needle: str
:rtype: int
"""
m = len(haystack)
n = len(needle)
if m < n:
return -1
if n == 0:
return 0
for j in range(m-n+1):
for i in range(n):
if needle[i] != haystack[i+j]:
break
if needle[i] == haystack[i+j]:
return j
return -1
方法2: java version 1
public int strStr(String source, String target){
if (source == null || target == null) return -1;
if (target.length() == 0) return 0;
int N = source.length();
int M = target.length();
int i, j;
int[][] dfa = buildDFA(target);
for(i = 0, j = 0; i < N && j < M; i++){
j = dfa[source.charAt(i)][j];
}
if (j == M ) return i - j;
else return -1;
}
public int[][] buildDFA(String target){
int M = target.length();
int R = 256;
int[][] dfa = new int[R][M];
dfa[target.charAt(0)][0] = 1;
for(int X = 0, j = 1; j < M; j++){
for(int i = 0; i < R; i++){
dfa[i][j] = dfa[i][X];
}
dfa[target.charAt(j)][j] = j + 1;
X = dfa[target.charAt(j)][X];
}
return dfa;
}
Leetcode 28. Implement strStr()
原文：http://www.cnblogs.com/nobody2somebody/p/5144551.html