Day 5

I hope you had a good weekend (and Monday) I didn't have the time to write the posts of this weekend but I did have the time to code...so there is day 5 !!

Details

• Asked by: Dropbox
• Difficulty: Hard

Problem

Implement an efficient string matching algorithm.

Given a string of length N and a pattern of length k, write a program that searches for the pattern in the string with less than O(N * k) worst-case time complexity.

If the pattern is found, return the start index of its location. If not, return False.

My solution

Nothing really special about this one. Sadly, because of the ".length" I'm not under O(N*k).

/**
 * Search pattern into searchIn
 *
 * @param searchIn 
 * @param pattern substring to find in searchIn
 * @return start index in string of the pattern, null if not found
 */
fun find(searchIn: String, pattern: String): Int? {
    for (i in 0 until searchIn.length - pattern.length){
        for ((index, c) in pattern.withIndex()){
            if (searchIn[i + index] != c)
                break
            else if(index == pattern.length - 1)
                return i
        }
    }
    return null
}

Now I have a class, so see you tomorrow! 😃