6.13 Find first occurence of string

#1

Just wondering if Robin Karp was used for this just for introducing the algorithm, as finding just the first occurence can be done with O(n) as below:

public static int find(String str, String sub) {
    int res = 0, curr = 0, offset = 0;
    for(int i = 0; i < str.length(); i++) {
        if(str.charAt(i) == sub.charAt(curr)) {
            if(curr + 1 == sub.length()) return i - offset - 1;
            curr++;
            offset++;
        }
        offset = 0;
    }
    return -1;
}
0 Likes
#2

Hi @ckkc00,

Thanks for your sharing. However, I am not very sure it works for this problem as yours does not traversal sub to making sure all characters in sub appears in str. Therefore, I think your algorithm won’t work.

0 Likes