Find the Index of the First Occurrence in a String

Problem

Given two strings needle and haystack, return the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.

Returns the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.

Clarification:

What should we return when needle is an empty string? This is a great question to ask during an interview.

For the purpose of this problem, we will return 0 when needle is an empty string. This is consistent to C’s strstr() and Java’s indexOf().

What if both haystack and needle are empty?

Examples

Example 1:

1
2

Input: haystack = "hello", needle = "ll"
Output: 2

Example 2:

1
2

Input: haystack = "aaaaa", needle = "bba"
Output: -1

Solution

Here are all the methods. We will use the signature:

1
2
3
4
5

public class Solution {
    public int strStr(String haystack, String needle) {
		
    }
}

Method 1 - Naive

• Naive Brute Force String Search Algorithm
• If pattern has all distinct chars - Optimized Brute Force String Search Algorithm

Method 2 - Rabin Karp Algorithm

Rabin-Karp Algorithm Explained

Method 3 - Morris Pratt

Morris-Pratt String Searching

Method 4 - Knuth Morris Pratt

Knuth Morris Pratt KMP Algorithm

Method 5 - Boyer Moore Algo

Boyer-Moore String Searching

Method 6 - Z algo

Z Algorithm String Searching

Method. 7 - Using Suffix tree

• Suffix Tree Data Structure DS Index
• String Pattern matching using suffix tree

1

[[4.data-structure-based-string-search]]

Parse the expression as tree Pattern Matching - Regular expression, deterministic and non-deterministic finite automaton (DFA and NFA)