content: package interviews.remotebase.live_coding_interview.questions;
  
  public class Question1 {
      public static void search(String pattern, String txt)
      {
          int M = pattern.length();
          int N = txt.length();
  
          // create lps[] that will hold the longest
          // prefix suffix values for pattern
          int lps[] = new int[M];
          int j = 0; // index for pat[]
  
          // Preprocess the pattern (calculate lps[]
          // array)
          computeLPSArray(pattern, M, lps);
  
          int i = 0; // index for txt[]
          boolean notFound = true;
          while ((N - i) >= (M - j)) {
              if (pattern.charAt(j) == txt.charAt(i)) {
                  j++;
                  i++;
              }
              if (j == M) {
                  System.out.println("Found pattern "
                          + "at index " + (i - j));
                  notFound = false;
                  j = lps[j - 1];
              }
  
              // mismatch after j matches
              else if (i < N
                      && pattern.charAt(j) != txt.charAt(i)) {
                  // Do not match lps[0..lps[j-1]] characters,
                  // they will match anyway
                  if (j != 0)
                      j = lps[j - 1];
                  else
                      i = i + 1;
              }
          }
          if (notFound){
              System.out.println("No Pattern Found");
          }
      }
  
      private static void computeLPSArray(String pat, int M, int lps[])
      {
          // length of the previous longest prefix suffix
          int len = 0;
          int i = 1;
          lps[0] = 0; // lps[0] is always 0
  
          // the loop calculates lps[i] for i = 1 to M-1
          while (i < M) {
              if (pat.charAt(i) == pat.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++;
                  }
              }
          }
      }
  }
  