Substring Searching

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

(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.

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

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

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?

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

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.

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

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

Why don't we have other programming languages which are so common? for e.g. C#, Java, C, C++ etc?