Question

Suppose we have a substring of length m and text of size n. Write an algorithm to find out if the substring is present in the text or not. What is the complexity of your algorithm in terms of m and n.

Answer 1

Algorithm for the above question is provided below.

// Check substring is present in text
boolean isSubstringPresent(string substring, string text)
  
   // Find the length of substring
   Find the length of substring and store in variable m
  
   // Find the length of text
   Find the length of text and store in variable n
  
   // Loop through the text
   For i=0 to n-m
  
       // Loop through the substring
       For j=0 to m
      
           // If do not match break from the loop
           if text(i+j)!=substring(j)
               break;
      
       // if the substring matches
       if j=m
      
           // Return true
           return true
          
   //    Return false
   return false

Running time complexity:

The outer for loop parse fro 0 to n-m.

The inner for loop parse through 0 to m.

So the running time complexity = O((n-m)*m) =O(nm)