BiruLyu
5/24/2017 - 7:29 PM

## 28. Implement strStr().java

``````
def kmp_matcher(text, pattern):
pi = compute_prefix_function(pattern)
matched = 0
for i, char in enumerate(text):
while matched > 0 and pattern[matched] != text[i]:
matched = pi[matched - 1]
if pattern[matched] == text[i]:
matched += 1
if matched == len(pattern):
return i - len(pattern) + 1
return -1

def compute_prefix_function(pattern):
pi = [0 for i in range(len(pattern))]
matched = 0
for i in range(1, len(pattern)):
while matched > 0 and pattern[i] != pattern[matched]:
matched = pi[matched - 1]
if pattern[i] == pattern[matched]:
matched += 1
pi[i] = matched
return pi``````
``````public int strStr(String haystack, String needle) {
for (int i = 0; ; i++) {
for (int j = 0; ; j++) {
if (j == needle.length()) return i;
if (i + j == haystack.length()) return -1;
if (needle.charAt(j) != haystack.charAt(i + j)) break;
}
}
}``````
``````/*
Prefix function of Pattern String
"abcdeabeabc"
a b c d e a b e a b c
[0,0,0,0,0,1,2,0,1,2,3]

"AAACAAAA"
A  A  A  C  A  A  A  A
[0, 1, 2, 0, 1, 2, 3, 3]

Part1. def get_prefix_function

Part2. def kmp_macher
k = 0
for i in range(len(Text)):
while(k > 0 and Text[i] != Pattern[k]):
k = prefix_funtion[k - 1]]
if Text[i] == Pattern[k]:
k += 1;
if k == len(Pattern)
return i - k + 1;
return -1

*/
public class Solution {

public int[] getPrefixFunction(String pattern){
int[] lps = null;
//// length of the previous longest prefix suffix
if(pattern == null || pattern.length() == 0) return lps;

lps = new int[pattern.length()];
lps[0] = 0;// lps[0] is always 0
int i = 1;
int len = 0;

// the loop calculates lps[i] for i = 1 to M-1
while (i < pattern.length()) {

if (pattern.charAt(i) == pattern.charAt(len)){
len++;
lps[i] = len;
i++;
} else {// (pat[i] != pat[len])

// This is tricky. Consider the example.
// AAACAAAA and i = 7. The idea is similar
// to search step.
if (len != 0){
len = lps[len-1];

// Also, note that we do not increment
// i here
} else { // if (len == 0)
lps[i] = len;
i++;
}
}
}

return lps;
}

public int strStr(String haystack, String needle) {
int lenOfStack = haystack.length();
int lenOfNeedle = needle.length();

if(lenOfNeedle == 0) return 0;
if(lenOfStack < lenOfNeedle) return -1;

int[] lps = getPrefixFunction(needle);
int k = 0;

for (int i = 0; i < lenOfStack; i++){
while(k > 0 && haystack.charAt(i) != needle.charAt(k)){
k = lps[k - 1];
}
if( haystack.charAt(i) == needle.charAt(k)){
k++;
}
if( k == lenOfNeedle){
return i - k + 1;
}
}

return -1;
}

}``````
``````class Solution(object):
def strStr(self, haystack, needle):
"""
:type haystack: str
:type needle: str
:rtype: int
"""

h = len(haystack);
n = len(needle);

if n > h :
return -1;

for i in range(h - n + 1):
if haystack[i: i + n] == needle:
return i;

return -1;``````
``````class Solution {
/**
* Returns a index to the first occurrence of target in source,
* or -1  if target is not part of source.
* @param source string to be scanned.
* @param target string containing the sequence of characters to match.
*/
public int strStr(String source, String target) {
if (source == null || target == null) {
return -1;
}

for (int i = 0; i < source.length() - target.length() + 1; i++) {
int j = 0;
for (j = 0; j < target.length(); j++) {
if (source.charAt(i + j) != target.charAt(j)) {
break;
}
}
// finished loop, target found
if (j == target.length()) {
return i;
}
}
return -1;
}
}``````