[Two Pointers] Implement strStr()

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