Index of the First Occurrence of pattern in a text

Summary

Find the index of the first occurrence of a given pattern in a text. This problem involves string matching and requires an efficient algorithm to locate the pattern in the text.

Detailed Explanation

To solve this problem, we can use the KMP (Knuth-Morris-Pratt) algorithm, which is an efficient string searching algorithm that uses a preprocessing step to construct a lookup table for the pattern. The time complexity of the KMP algorithm is O(n + m), where n is the length of the text and m is the length of the pattern.

Here's a step-by-step breakdown of the solution:

Preprocess the pattern to construct a lookup table. This table, called the "failure function," stores the longest proper prefix that is also a suffix for each substring of the pattern.
Initialize two pointers, one at the start of the text and one at the start of the pattern.
Compare characters at the current positions in the text and pattern.
If the characters match, move both pointers one step forward.
If the characters don't match, use the failure function to determine how many characters to skip in the pattern before moving the pointer.
Repeat steps 3-5 until the end of the pattern is reached or a mismatch is found.

Time complexity: O(n + m) Space complexity: O(m)

Here's an ASCII art diagram illustrating the KMP algorithm:

Text:  |a|b|c|d|e|
Pattern: |a|b|c|  |
       ^  ^
       |  skip 2 characters in pattern
       v  v
Text:  |a|b|c|d|e|f|g|h|i|
Pattern: |a|b|c|  |
       ^  ^
       |  skip 1 character in pattern
       v  v

Optimized Solutions

Java

public class FirstOccurrenceIndex { public static int firstOccurrenceIndex(String text, String pattern) { int[] failureFunction = getFailureFunction(pattern); int j = 0; for (int i = 0; i < text.length(); i++) { while (j > 0 && text.charAt(i) != pattern.charAt(j)) { j = failureFunction[j - 1]; } if (text.charAt(i) == pattern.charAt(j)) { j++; } if (j == pattern.length()) { return i - j + 1; } } return -1; // not found } public static int[] getFailureFunction(String pattern) { int[] failureFunction = new int[pattern.length()]; int j = 0; for (int i = 1; i < pattern.length(); i++) { while (j > 0 && pattern.charAt(i) != pattern.charAt(j)) { j = failureFunction[j - 1]; } if (pattern.charAt(i) == pattern.charAt(j)) { j++; } } return failureFunction; } }