Question

Task Algorithms: Pattern Matching (in java)

Write a program that gets two strings from user, size and pattern, and checks if pattern exists inside size, if it exists then program returns index of first character of pattern inside size, otherwise it returns -1.

The method should not use built-in methods such as indexOf , find, etc. Only charAt and length are allowed to use.

Analyze the time complexity of your algorithm.

Your solution is not allowed to be> = O (m * n), it should be O (n) (where n is the length of the string being searched).

Hint:
The most intuitive solution will be two loops, one inside the other. This will not give O (N) behavior. It holds with one for loop; one index that runs through the string where we search and another index for the substring.

Feel free to solve the problem by implementing "brute force" / naive solution (the one with two loops) first, based on this you can solve the problem by reducing to just a loop and a bit smarter code.

Hint / partial pseudo code for an O (n) solution:
A counter k keeps track of the number of characters with a match, when this is equal to the length of the pattern we have a match

k = 0; 
for (iterates over the string we are searching in, from index 0) 
  if (k == length pattern) 
    returns index of start match 
  else 
    if characters in search string match characters in pattern 
      k ++; 
    else 
      k = 0;

..and then we have to treat a special case if k was incremented but for the loop terminated

Extra, as a challenge: Why not try to understand, and then implement the Boyer-Moore-Horspool algorithm?

Answer 1

// Recursive Java program to check if a string
// is subsequence of another string
import java.io.*;

class SubSequence
{
   // Returns true if str1[] is a subsequence of str2[]
   // m is length of str1 and n is length of str2
   static boolean isSubSequence(String str1, String str2, int m, int n)
   {
       // Base Cases
       if (m == 0)
           return true;
       if (n == 0)
           return false;
          
       // If last characters of two strings are matching
       if (str1.charAt(m-1) == str2.charAt(n-1))
           return isSubSequence(str1, str2, m-1, n-1);

       // If last characters are not matching
       return isSubSequence(str1, str2, m, n-1);
   }
  
   // Driver program
   public static void main (String[] args)
   {
       String str1 = "gksrek";
       String str2 = "geeksforgeeks";
       int m = str1.length();
       int n = str2.length();
       boolean res = isSubSequence(str1, str2, m, n);
       if(res)
           System.out.println("Yes");
       else
           System.out.println("No");
   }
}

// Iterative Java program to check if a string
// is subsequence of another string
import java.io.*;

class GFG {
  
   // Returns true if str1[] is a subsequence
   // of str2[] m is length of str1 and n is
   // length of str2
   static boolean isSubSequence(String str1,
                   String str2, int m, int n)
   {
       int j = 0;
      
       // Traverse str2 and str1, and compare
       // current character of str2 with first
       // unmatched char of str1, if matched
       // then move ahead in str1
       for (int i = 0; i < n && j < m; i++)
           if (str1.charAt(j) == str2.charAt(i))
               j++;

       // If all characters of str1 were found
       // in str2
       return (j == m);
   }
  
   // Driver program to test methods of
   // graph class
   public static void main (String[] args)
   {
       String str1 = "gksrek";
       String str2 = "geeksforgeeks";
       int m = str1.length();
       int n = str2.length();
       boolean res = isSubSequence(str1, str2, m, n);
      
       if(res)
           System.out.println("Yes");
       else
           System.out.println("No");
   }
}