Implement strstr function in Java

Write an efficient algorithm to implement strstr function in Java which returns the index of first occurrence of a string in another string.

 
 

The prototype of strstr() function is : int strstr(String X, String Y);

 

1. Iterative Implementation (Naive)

Here’s iterative implementation of the strstr(X, Y) function. It returns the index of the first occurrence of Y in X or -1 if Y is not part of X.

 

Download   Run Code

Output:

Index of first occurrence of Y in X is 9

 
The time complexity of this solution is O(mn) where m and n are length of String X and Y respectively.

 

2. Recursive Implementation

Below is recursive Implementation of above code, but it returns the substring starting at the first occurrence of Y in X.

 

Download   Run Code

Output:

9

 
The time complexity of this solution remains O(mn) but it also uses some extra space for recursive calls.

 

3. Using KMP Algorithm (Efficient)

 
We can even use KMP Algorithm to solve this problem which offers O(m + n) complexity where m and n are lengths of String X and Y respectively.

 

Download   Run Code

Output:

Index of first occurrence of Y in X is 9

 
Also See: Implement strstr() function in C (Iterative & Recursive)

 
Thanks for reading.




Please use ideone or C++ Shell or any other online compiler link to post code in comments.
Like us? Please spread the word and help us grow. Happy coding 🙂
 





Leave a Reply

Notify of
avatar
wpDiscuz