Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import Data.List
- main = do
- tCases <- getLine
- ll <- (allCases (read tCases :: Int) [])
- putStr $ unlines ll
- allCases :: Int -> [String] -> IO [String]
- allCases _T sa
- | _T<=0 = return sa
- | _T >0 = do
- r1 <- oneCase
- allCases (_T-1) (sa ++ [r1])
- oneCase :: IO String -- "YES" or "NO"
- oneCase = do
- g <- getGrid -- main grid
- p <- getGrid -- pattern
- return (foundIt (g,p))
- getGrid :: IO [String]
- getGrid = do
- l <- getLine
- let [r,c] = map (\x -> read x :: Int) $ words l
- rows :: Int -> [String] -> IO [String]
- rows r g| r<=0 = return g
- | otherwise = do
- rl <- getLine
- rows (r-1) (g ++ [rl])
- rows r []
- breakAt :: String -> String -> (String,String)
- breakAt c [] = ("","")
- breakAt [] s = ("",s)
- breakAt c s =
- let b' (j,"") = (j,"")
- b' (j,w@(c1:cs))
- | isPrefixOf c w = (j,w)
- | otherwise = b' (j++[c1],cs)
- in b' ("",s)
- foundIt :: ([String],[String]) -> String
- foundIt ([],_) = "NO"
- foundIt (_,[]) = "YES"
- foundIt (g@(gl:gls),p@(pl:pls)) =
- let s@(ii,sf) = breakAt pl gl
- ix = length ii
- in if sf /= "" -- match was found, ix=offset of pl in gl
- then foundIt $ chkP (g, p) ix -- try to match the rest
- else foundIt (gls,p) -- try the next line in the grid
- chkP :: ([String],[String]) -> Int -> ([String],[String])
- -- if chkP finds the pattern in the grid, it returns (_,[])
- -- if it doesn't find it, it returns the grid with the headprefix + 1
- -- digit marked out, and the entire pattern
- -- if the pattern is longer than the remaining grid, returns ([],p)
- chkP w@(g,p) ix =
- if length g < length p
- then ([],p)
- else
- let g0 = ((replicate (ix+1) '~')++(drop (ix+1) (head g))):tail g
- chkP' (_,[]) = (g0,[]) -- all pattern lines succeeded
- chkP' ([],_) = (g0,p) -- end of grid, no match
- chkP' (gr@(g1:g1s),pt@(p1:p1s))
- | isPrefixOf p1 (drop ix g1) = chkP' (g1s,p1s)
- | otherwise = (g0,p)
- in chkP' w
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement