Find index of substring in another string Haskell

Question

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 :)

Don't use !!. Rather, proceed by recursion on the second string. If f "oo" "foobar" is [(1,2)], how to change that list to have the correct result for f "oo" "ofoobar"? What about f "oo" "oofoobar"? Think about how to re-use the result for the tail so to obtain the result for the one-char-longer string. Using map might help, as well as isPrefix. — chi
– chi, Commented Sep 15, 2021 at 11:06

willeM_ Van Onsem · Accepted Answer · 2021-09-15 11:06:17Z

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.

Collectives™ on Stack Overflow

Find index of substring in another string Haskell

1 Answer 1

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related