Advertisement
Guest User

Untitled

a guest
Jan 11th, 2016
434
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.14 KB | None | 0 0
  1. import Data.List
  2.  
  3. main = do
  4. tCases <- getLine
  5. ll <- (allCases (read tCases :: Int) [])
  6. putStr $ unlines ll
  7.  
  8. allCases :: Int -> [String] -> IO [String]
  9. allCases _T sa
  10. | _T<=0 = return sa
  11. | _T >0 = do
  12. r1 <- oneCase
  13. allCases (_T-1) (sa ++ [r1])
  14.  
  15. oneCase :: IO String -- "YES" or "NO"
  16. oneCase = do
  17. g <- getGrid -- main grid
  18. p <- getGrid -- pattern
  19. return (foundIt (g,p))
  20.  
  21. getGrid :: IO [String]
  22. getGrid = do
  23. l <- getLine
  24. let [r,c] = map (\x -> read x :: Int) $ words l
  25. rows :: Int -> [String] -> IO [String]
  26. rows r g| r<=0 = return g
  27. | otherwise = do
  28. rl <- getLine
  29. rows (r-1) (g ++ [rl])
  30. rows r []
  31.  
  32. breakAt :: String -> String -> (String,String)
  33. breakAt c [] = ("","")
  34. breakAt [] s = ("",s)
  35. breakAt c s =
  36. let b' (j,"") = (j,"")
  37. b' (j,w@(c1:cs))
  38. | isPrefixOf c w = (j,w)
  39. | otherwise = b' (j++[c1],cs)
  40. in b' ("",s)
  41.  
  42. foundIt :: ([String],[String]) -> String
  43. foundIt ([],_) = "NO"
  44. foundIt (_,[]) = "YES"
  45. foundIt (g@(gl:gls),p@(pl:pls)) =
  46. let s@(ii,sf) = breakAt pl gl
  47. ix = length ii
  48. in if sf /= "" -- match was found, ix=offset of pl in gl
  49. then foundIt $ chkP (g, p) ix -- try to match the rest
  50. else foundIt (gls,p) -- try the next line in the grid
  51.  
  52. chkP :: ([String],[String]) -> Int -> ([String],[String])
  53. -- if chkP finds the pattern in the grid, it returns (_,[])
  54. -- if it doesn't find it, it returns the grid with the headprefix + 1
  55. -- digit marked out, and the entire pattern
  56. -- if the pattern is longer than the remaining grid, returns ([],p)
  57. chkP w@(g,p) ix =
  58. if length g < length p
  59. then ([],p)
  60. else
  61. let g0 = ((replicate (ix+1) '~')++(drop (ix+1) (head g))):tail g
  62. chkP' (_,[]) = (g0,[]) -- all pattern lines succeeded
  63. chkP' ([],_) = (g0,p) -- end of grid, no match
  64. chkP' (gr@(g1:g1s),pt@(p1:p1s))
  65. | isPrefixOf p1 (drop ix g1) = chkP' (g1s,p1s)
  66. | otherwise = (g0,p)
  67. in chkP' w
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement