karoyakani
"Testcase 1" で Out of memory になるソースはこちらです ``` {-# LANGUAGE FlexibleInstances, UndecidableInstances, DuplicateRecordFields #-}
module Main where
import Control.Monad
import Data.Array
import Data.List
import System.Environment
import
substringDiff k s1 s2 = bsearch 1 (min n1 n2) f
where
n1 = length s1
n2 = length s2
ar1 = listArray (1,n1) s1
ar2 = listArray (1,n2) s2
ar = array ((0,0),(n1,n2)) $ ((0,0),0):
[((i,0),0) | i <- [1..n1]] ++ [((0,j),0) | j <- [1..n2]] ++
[((i,j),ar!(i-1,j-1) + if ar1!i == ar2!j then 0 else 1) | i <- [1..n1], j <- [1..n2]]
f x = or [ar!(i,j) - ar!(i-x,j-x) <= k | i <- [x..n1], j <- [x..n2], x <= min i j]
bsearch l r p
| l >= r = l
| p m = bsearch m r p
| otherwise = bsearch l (m-1) p
where m = (l+r+1) `div` 2
main :: IO()
main = do
stdout <- getEnv "OUTPUT_PATH"
fptr <- openFile stdout WriteMode
t <- readLn :: IO Int
forM_ [1..t] $ \t_itr -> do
kS1S2Temp <- getLine
let kS1S2 = words kS1S2Temp
let k = read (kS1S2 !! 0) :: Int
let s1 = kS1S2 !! 1
let s2 = kS1S2 !! 2
let result = substringDiff k s1 s2
hPutStrLn fptr $ show result
hFlush fptr
hClose fptr
```
module Main where
import Control.Monad
import Data.Array
import Data.List
import System.Environment
import
substringDiff k s1 s2 = bsearch 1 (min n1 n2) f
where
n1 = length s1
n2 = length s2
ar1 = listArray (1,n1) s1
ar2 = listArray (1,n2) s2
ar = array ((0,0),(n1,n2)) $ ((0,0),0):
[((i,0),0) | i <- [1..n1]] ++ [((0,j),0) | j <- [1..n2]] ++
[((i,j),ar!(i-1,j-1) + if ar1!i == ar2!j then 0 else 1) | i <- [1..n1], j <- [1..n2]]
f x = or [ar!(i,j) - ar!(i-x,j-x) <= k | i <- [x..n1], j <- [x..n2], x <= min i j]
bsearch l r p
| l >= r = l
| p m = bsearch m r p
| otherwise = bsearch l (m-1) p
where m = (l+r+1) `div` 2
main :: IO()
main = do
stdout <- getEnv "OUTPUT_PATH"
fptr <- openFile stdout WriteMode
t <- readLn :: IO Int
forM_ [1..t] $ \t_itr -> do
kS1S2Temp <- getLine
let kS1S2 = words kS1S2Temp
let k = read (kS1S2 !! 0) :: Int
let s1 = kS1S2 !! 1
let s2 = kS1S2 !! 2
let result = substringDiff k s1 s2
hPutStrLn fptr $ show result
hFlush fptr
hClose fptr
```