findRule = chk [] . rec
  where
    rec [] = []
    rec (x:xs) = case span (/=x) xs of (as,bs) -> (x:as) : rec bs
    chk _ [] = []
    chk key (x:xs)
      | and $ zipWith (==) xs $ cycle k = concat k
      | otherwise = chk k xs
      where
        k = key ++ [x]
 
main :: IO ()
main = test
 
test = do
  let s ==> t = print $ findRule s == t
  "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa" ==> "a"
  "123412312341231234123123412312341231234123" ==> "1234123"
  "oxoxoxoxoxoxoxoxxoxoxoxoxoxoxoxoxx" ==> "oxoxoxoxoxoxoxoxx"
  "axaxa" ==> "axaxa"
  "" ==> ""
 

ZmluZFJ1bGUgPSBjaGsgW10gLiByZWMKICB3aGVyZQogICAgcmVjIFtdID0gW10KICAgIHJlYyAoeDp4cykgPSBjYXNlIHNwYW4gKC89eCkgeHMgb2YgKGFzLGJzKSAtPiAoeDphcykgOiByZWMgYnMKICAgIGNoayBfIFtdID0gW10KICAgIGNoayBrZXkgKHg6eHMpCiAgICAgIHwgYW5kICQgemlwV2l0aCAoPT0pIHhzICQgY3ljbGUgayA9IGNvbmNhdCBrCiAgICAgIHwgb3RoZXJ3aXNlID0gY2hrIGsgeHMKICAgICAgd2hlcmUKICAgICAgICBrID0ga2V5ICsrIFt4XQoKbWFpbiA6OiBJTyAoKQptYWluID0gdGVzdAoKdGVzdCA9IGRvCiAgbGV0IHMgPT0+IHQgPSBwcmludCAkIGZpbmRSdWxlIHMgPT0gdAogICJhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYWFhYSIgPT0+ICJhIgogICIxMjM0MTIzMTIzNDEyMzEyMzQxMjMxMjM0MTIzMTIzNDEyMzEyMzQxMjMiID09PiAiMTIzNDEyMyIKICAib3hveG94b3hveG94b3hveHhveG94b3hveG94b3hveG94eCIgPT0+ICJveG94b3hveG94b3hveG94eCIKICAiYXhheGEiID09PiAiYXhheGEiCiAgIiIgPT0+ICIiCg==