CODEWITHSUNDEEP
haskell
Anders Stene
Anders Stene

Reputation: 149

Find index of substring in another string Haskell

I am to make a function which takes two parameters (Strings). The function shall see if the first parameter is a substring of the second parameter. If that is the case, it shall return tuples of each occurences which consists of the startindex of the substring, and the index of the end of the substring. For example:

f :: String -> String -> [(Int,Int)]
f "oo" "foobar" = [(1,2)]
f "oo" "fooboor" = [(1,2),(4,5)]
f "ooo" "fooobar" = [(1,3)]

We are not allowed to import anything, but I have a isPrefix function. It checks if the first parameter is a prefix to the second parameter.

isPrefix :: Eq a => [a] -> [a] -> Bool 
isPrefix [] _ = True
isPrefix _ [] = False
isPrefix (x:xs) (y:ys) |x== y = isPrefix xs ys
                       |otherwise = False

I was thinking a solution may be to run the function "isPrefix" first on x, and if it returns False, I run it on the tail (xs) and so on. However, I am struggling to implement it and struggling to understand how to return the index of the string if it exists. Perhaps using "!!"? Do you think I am onto something? As I am new to Haskell the syntax is a bit of a struggle :)

Upvotes: 4

Views: 1381

Answers (1)

willeM_ Van Onsem
willeM_ Van Onsem

Reputation: 476547

We can make a function that will check if the first list is a prefix of the second list. If that is the case, we prepend (0, length firstlist - 1) to the recursive call where we increment both indexes by one.

Ths thus means that such function looks like:

f :: Eq a => [a] -> [a] -> [(Int, Int)]
f needle = go
  where go [] = []
        go haystack@(_: xs)
            | isPrefix needle haystack = (…, …) : tl  -- (1)
            | otherwise = tl
          where tl = … (go xs)                        -- (2)
        n = length needle

Here (1) thus prepends (…, …) to the list; and for (2) tl makes a recursive call and needs to post-process the list by incrementing both items of the 2-tuple by one.

There is a more efficient algorithm to do this where you pass the current index in the recursive call, or you can implement the Knuth-Morris-Pratt algorithm [wiki], I leave these as an exercise.

Upvotes: 1

Related Questions