1. Example
for (int i = 0 ; i <= haystack.length() - needle.length() ; i++)
for (int j = 0; j < needle.length(); j++)
haystack[i+j] == needle[j]
NOT EVERYTIME i++
while ( i <= haystack.length() - needle.length() )
for (int j = 0 ; j < needle.length();j++)
haystack[i+j] == needle[j]
if haystack and needle first char not match
i++;
break;
else
i += j - next[j-1];
break;
"issip"
00120
012345678910
"mississippi"
"issip"
"issip" i += j - next[j-1] = 4 -2= 2
issip
issipi
KMP
1. Prefix table
A C A C A G T
0 0 1 2 3 0 0
first char
no shift (0)
for each char, find the same letter before it and if found,
last char's shift +1
cannot find the same letter before it,
no shift (0)
i + j - ( prefixtable[j]-1 )
for (int i = 1; i < needle.length(); i++) {
int index = next[i - 1];
while (index > 0 && needle.charAt(index) != needle.charAt(i)) {
index = next[index - 1];
}
if (needle.charAt(index) == needle.charAt(i)) {
next[i] = next[i - 1] + 1;
} else {
next[i] = 0;
}
N A N O
0 0 1 0
2. How to do the skip (shift previous same letter(from prefix table) to mismatch index)
A C A C A G T
0 0 1 2 3 0 0
i=0 1 2 3
A C A T.....................
A1C1A2 C2
X
i=2
A1 C1
i = i+j - next[j-1] = 0+3 - 1 =2
String compare amongst more than two use
INDEX to record matched length
Succeed go to the end and not succeed break, use
BOOLEAN FLAG
return the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack
n="sub" h ="submarine"=> return 0
n="ood" h = "food" => return 1
2. Implementation
Q1: compare char to char from one to the other?
A1: Time:O(n*m), how many iterations, index 0 to index 0 and needle.length() to 0+needle.length
https://www.youtube.com/watch?v=2ogqPWJSftE
public int strStr(String haystack, String needle)
{
// validate the input
if (haystack == null || needle == null || neelde.length() ==0)
return 0;
if ( needle.length() > haystack.length() )
return -1;
int[] next = getNext(needle);
int i = 0;
// NOTE: since i will jump, we use while loop
while ( i <= haystack.length() - needle.length() )
{
boolean successFlag = true;
for ( int j = 0 ; j < needle.length() ; j++) {
// First letter mismatch, regular shift
if ( needle.charAt(0) != haystack.charAt(i) )
{
successFlag = false;
i++;
break;
}
// Other letter mismatch, jump shift
else if ( needle.charAt(j) != haystack.charAt(i+j) )
{
successFlag = false;
// NOTE:
i = i + j - next[j-1];
break;
}
}
if ( successFlag )
return i;
}
return -1;
}
// Calculate the prefix table,called next table here
public int[] getNext(String needle)
{
int[] next = new int[needle.length()];
next[0] = 0;
for (int i =1 ; i < needle.length(); i++)
{
int index = next[i-1];
// Case1: index > 0, search back to find same letter
while ( index > 0 && needle.charAt(index) != needle.charAt(i) )
index = next[index-1];
//Case2: index=0 or others, compare with the index letter and based on it plus 1
if (needle.charAt(index) == needle.charAt(i))
next[i] = next[i-1] + 1;
else
next[i] = 0;
}
return next;
}
// Time:O(m*n), Space:O(1)
public int strStr( String haystack, String needle)
{
// Validate the input
if (haystack == null || needle == null || needle.length() == 0)
return 0;
if (needle.length() > haystack.length())
return -1;
//int index = 0;
//NOTE: haystack.length()-1==== needle.length()-1
// hay-1-needle+1=hay-needle(include) 0(include)
for (int i = 0 ; i <= haystack.length() - needle.length() ; i++)
{
// NOTE: to record in case, once false, we are done
boolean successFlag = true;
for (int j =0; i < needle.length(); j++)
{
if (needle.charAt(j)!=haystack.charAt(i+j))
{
break;
successFlag = false;
}
//index++;
}
//if (index == needle.length())
// return i;
if (successFlag)
return i;
}
return -1;
}
// Time:O(m+n), Space:O(1)
public int strStr(String haystack, String needle)
{
// validate the input
if ( haystack==null || needle == null || neelde.length()==0)
return 0;
if ( needle.length() > haystack.length() )
return -1;
// NOTE: when doing shift in the haystack, every s hift remvoe previous first char and add a new last char
// NOTE: abc = 0*29^2 + 1*29^1 + 2*1
int base = 29;
int temp = 1;
int hashcode = 0;
for ( int i = needle.length()-1; i >= 0 ; i++)
{
hashcode+ = (int)(needle.charAt(i)-'a')*temp;
temp*=base;
}
int temp2 =1;
int hashcode2 = 0;
for(int j = needle.length()-1;j>=0;j++)
{
hashcode2+= (int)(haystack.charAt(i)-'a')*temp2;
temp2*=base;
}
if (hashcode == hashcode2)
return 0;
temp2/=base;
//for (int i = 1; i <= haystack.length() - needle.length();i++)
//{
// hashcode2 = (hashcode2 - haystack.charAt(i-1)*temp2)*base + haystack.charAt(i+needle.length()-1);
// if (hashcode == hashcode2)
// return i;
//}
// NOTE: start form the last new element
for (int i=needle.length(); i < haystack.length();i++)
{
hashcode2 = ( hashcode2 - haystack.charAt(i-needle.length()*temp2) )*base + haystack.charAt(i);
return i-needle.length()+1;
}
return -1;
}
3. Similar ones
(H) Shortest Palindrome
