Implement strstr function in Java
Write an efficient algorithm to implement the strstr function in Java, which returns the index of the first occurrence of a string in another string.
The prototype of the strstr() function is int strstr(String X, String Y);
1. Iterative Implementation (Naive)
Here’s an 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.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 |
class Main { // Function to implement `strstr()` function public static int strstr(String X, String Y) { // if `X` is null or if X's length is less than that of Y's if (X == null || Y.length() > X.length()) { return -1; } // if `Y` is null or is empty if (Y == null || Y.length() == 0) { return 0; } for (int i = 0; i <= X.length() - Y.length(); i++) { int j; for (j = 0; j < Y.length(); j++) { if (Y.charAt(j) != X.charAt(i + j)) { break; } } if (j == Y.length()) { return i; } } return -1; } public static void main(String[] args) { String X = "Techie Delight"; String Y = "light"; System.out.println("The index of the first occurrence of Y in X is " + strstr(X, Y)); } } |
Output:
The index of the first occurrence of Y in X is 9
The time complexity of this solution is O(m.n) where m and n are the length of string X and Y, respectively.
2. 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.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 |
class Main { // Function to implement `strstr()` function using KMP algorithm public static int strstr(String X, String Y) { // base case 1: `Y` is null or empty if (Y == null || Y.length() == 0) { return 0; } // base case 2: `X` is null, or X's length is less than Y's if (X == null || Y.length() > X.length()) { return -1; } char[] chars = Y.toCharArray(); // `next[i]` stores the index of the next best partial match int[] next = new int[Y.length() + 1]; for (int i = 1; i < Y.length(); i++) { int j = next[i]; while (j > 0 && chars[j] != chars[i]) { j = next[j]; } if (j > 0 || chars[j] == chars[i]) { next[i + 1] = j + 1; } } for (int i = 0, j = 0; i < X.length(); i++) { if (j < Y.length() && X.charAt(i) == Y.charAt(j)) { if (++j == Y.length()) { return (i - j + 1); } } else if (j > 0) { j = next[j]; i--; // as `i` will be incremented in the next iteration } } return -1; } public static void main(String[] args) { String X = "Techie Delight"; String Y = "light"; System.out.println("The index of the first occurrence of Y in X is " + strstr(X, Y)); } } |
Output:
The index of the first occurrence of Y in X is 9
Also See:
Thanks for reading.
To share your code in the comments, please use our online compiler that supports C, C++, Java, Python, JavaScript, C#, PHP, and many more popular programming languages.
Like us? Refer us to your friends and support our growth. Happy coding :)