# Substring Searching

# Substring Searching

gschoen + 0 comments It took me a while to master the concept of the KMP algorithm but once I did, it was fairly straightforward to code the algorithm. The link provided didn't give a very clear explanation but there are many references on google/YouTube that did.

No credit to Hackerrank for providing a test case #0 that had no pattern strings with repetitions in them. One should not have to buy a test case to test the implementation of the pattern matching array.

I'm not sure that a program that modifies the elements of the pattern matching array counts as "functional" programming. I could have buried this inside a function that generates the array to begin with and made it look to the outside world as purely functional. I didn't bother with this deception.(defun make-shifts (j i pattern shifts) (cond ((zerop i) (setf (aref shifts 0) 0) (make-shifts 0 1 pattern shifts)) ((>= i (length pattern)) shifts) ((eq (char pattern i) (char pattern j)) (setf (aref shifts i) (1+ (aref shifts j))) (make-shifts (1+ j) (1+ i) pattern shifts)) (T (cond ((zerop j) (setf (aref shifts i) 0) (make-shifts 0 (1+ i) pattern shifts)) (T (make-shifts (aref shifts (1- j)) i pattern shifts)))))) (defun find-pattern (i j str patt shifts) (cond ((> i (- (length str) (length patt))) nil) ((>= j (length patt)) T) ((eq (char str (+ i j)) (char patt j)) (find-pattern i (1+ j) str patt shifts)) ((zerop j) (find-pattern (1+ i) j str patt shifts)) (T (find-pattern (+ i (- j (aref shifts (1- j)))) (aref shifts (1- j)) str patt shifts)))) (defun cases (n) (cond ((zerop n) nil) (T (let* ((s (read-line)) (p (read-line)) (sh (make-shifts 0 0 p (make-array (length p))))) (if (find-pattern 0 0 s p sh) (format t "YES~%") (format t "NO~%"))) (cases (1- n))))) (cases (read))

paolo_veronelli + 0 comments Amazing, I really enjoyed this and yes it has functional solutions. Have fun!

sherub_thakur + 0 comments (Obvious Observation): There is no editorial on this problem. Would really appreciate if there was one as I would like to see how to solve this problem in O(n + m) purely functionally as I just chickened out and used ST monad.

wizard2none + 0 comments This provides great description of KMP which can be recoded in your language of choice.

Leeeeeee + 0 comments this is my solution , but test case 5 got wrong,I download the test case file,but the result is right,I dont know why

{-# LANGUAGE OverloadedStrings #-} module Main where import Control.Monad import qualified Data.ByteString as B import qualified Data.ByteString.Char8 as S8 import Debug.Trace issub x y |S8.null x = False |S8.null y =True |S8.head x ==S8.head y = if flag then True else issub (S8.drop sameLeng x) y |otherwise =issub xs y where xs = S8.tail x ys = S8.tail y need = S8.length ys zips = S8.zip x y sameLeng = 1+ length(takeWhile (\e->fst e == snd e) zips) flag = ys == S8.take need xs main = do line <-Prelude.getLine let num = read line arr <- forM [1..num] $ \_->do a<- S8.getLine b<- S8.getLine if (issub a b ) then return ("YES") else return ("NO") mapM_ putStrLn arr

ptvirgo + 0 comments It may be obvious that I'm new to Haskell.

Code: https://gist.github.com/ptvirgo/18b4a17b4a41e57298b0135e38097276

Been trying this for the past few days, taking advantage of online descriptions of the actual algorithm. Seems like I'm getting the answer right, but about half of the tests time out. Am I missing something?

mukeshsinghbhak1 + 0 comments cant improve the recursion in the below code ... gives timeout error.....

main = do n<-readLn fn n [] fn n rs = do if n>0 then do s1<-getLine s2<-getLine fn (n-1) (rs++[(s1,s2)]) else do let x = process rs putStrLn x

f' str sstr = f str sstr str sstr f [] _ _ _ = "YES" f _ [] _ _ = "NO"

f (x:xs) (y:ys) gs ls = if x==y then f xs ys gs ls else f gs (drop 1 ls) gs (drop 1 ls) process xs = unlines $ map ((x,y)->(f' y x)) xs

nkrim + 2 comments I've implemented this in Haskell exactly as the wikipedia article specified, but I'm timing out on the last 3 test cases.

I've had a similar experience with using haskell on hackerrank with other problems, where I feel like I've implemented it in the most efficient way, while also tacking on seemingly extraneous optimizations that seem above and beyond the scope of the problem in a lot of cases, and it still ends up timing out on the larger test cases.

If anyone has any insight on why this might be happening I'd greatly appreciate it.

anfelor + 1 comment I don't know your code, so I can't help you with that, but there are some hints I can give you:

Use recursion instead of IORefs/ST + Vector as Haskell is optimised for recursion and but not for IORefs.

Make sure, that nothing is loaded into memory completely. If you "consume" your strings instantly, the data will be streamed lazily from the console into your function which means less GC work.

Don't worry, I have these problems too sometimes!

Example:

kmp :: String -> String -> Bool kmp [] _ = False kmp str search = if search `isPrefixOf` str then True else kmp (tail str) search

Although being not the right algorithm, it fails only one test case.

anfelor + 0 comments In case you don't want to solve it by yourself, see: http://www.twanvl.nl/blog/haskell/Knuth-Morris-Pratt-in-Haskell

mukeshsinghbhak1 + 0 comments same with me

flopezlasanta + 1 comment My submission fails with the last test case only; I use Scala language; a first attempt was made without the table; I was expecting to pass the last test case in the second attempt because I included the table, but it did not work! any hints? BTW I use tail recursion for making the table and for checking if the pattern is present

flopezlasanta + 0 comments Nevermind... I just noticed the table is not built correctly; time to fix it

darklight + 0 comments What is expected of this problem in terms of functional structure? Can I use libraries to implement this? Because the code I wrote was more of non functional style

Sort 11 Discussions, By:

Please Login in order to post a comment