Naga Vara Pradeep, Yendluri

Find The Index Of The First Occurrence In A String

Given 2 strings - haystack and needle.

Problem statement

Find the index of needle substring if present in haystack and return starting index of the first occurrence, else return -1.

Idea is to iterate from 0 till length of haystack - length of needle, this will help us not to overrun the last index.

Algorithm
function find_occurence{
    loop i: 0 to haystack.length-needle.length{
    haystack.substring(i, i+needle.length) == needle
    return index
    }
    return -1
}

Example:

haystack: hadel, needle: ade

In first iteration,

haystack substring from 0, 0+3 is had.

checking had equal to ade

not equal going to next iteration.

Java Implementation

class Solution {
    public int strStr(String haystack, String needle) {
        // taking lengths of both the given strings
        int ln = needle.length();
        int lh = haystack.length();
        
        for (int i = 0; i <= lh - ln; i++) { 
            // checking if substring of haystack of size needle string from 
            // current index to the needle string.
            if (haystack.substring(i, i + ln).equals(needle)) { 
                // we found needle string in haystack, we'll
                return index i 
                // to save time and computation, since we only need index of 
                // first occurence. 
                return i; 
            } 
        } 
        // Finally we return -1 since we haven't found needle in haystack
        return -1; 
    } 
}