frequent-substring (empty) → 0.1.0.0
raw patch · 9 files changed
+647/−0 lines, 9 filesdep +HUnitdep +basedep +containers
Dependencies added: HUnit, base, containers, frequent-substring, hashable, optparse-applicative, text, text-replace
Files
- CHANGELOG.md +8/−0
- LICENSE +26/−0
- README.md +144/−0
- app/Main.hs +185/−0
- frequent-substring.cabal +89/−0
- src/FreqMap.hs +42/−0
- src/FrequentSubstring.hs +100/−0
- src/Util.hs +9/−0
- test/Spec.hs +44/−0
+ CHANGELOG.md view
@@ -0,0 +1,8 @@+# Changelog++## [0.1.0.0] - 2025-01-15+### Added+- Initial release of frequent-substring+++
+ LICENSE view
@@ -0,0 +1,26 @@+Copyright 2025 Matthew Herzl++Redistribution and use in source and binary forms, with or without+modification, are permitted provided that the following conditions are met:++1. Redistributions of source code must retain the above copyright notice, this+ list of conditions and the following disclaimer.++2. Redistributions in binary form must reproduce the above copyright notice,+ this list of conditions and the following disclaimer in the documentation+ and/or other materials provided with the distribution.++3. Neither the name of the copyright holder nor the names of its contributors+ may be used to endorse or promote products derived from this software+ without specific prior written permission.++THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND+ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED+WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE+DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE FOR+ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES+(INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;+LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON+ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT+(INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS+SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ README.md view
@@ -0,0 +1,144 @@+# frequent-substring++## Overview++`subs` is a tool for identifying frequent substrings in a text file, and substituting them for something else.+It is implemented in Haskell.++With the `-l` option, it can find the most frequent subsequence of a specified length.+With the `-r` option, it can find the longest subsequence that repeats at least the specified number of times.+With the `-s` option, in concert with the others, it can substitute the specified string for the subsequence found.++It works by hashing the subsequences that it's counting, to reduce memory consumption.+The motivating use-case was to aid in simplifying long mathematical expressions, too long for ordinary algebra systems (e.g. sage, mathematica) to simplify without exhausting memory.+It has successfully found a longest-substring on a >2.5M character sequence, which led to memory exhaustion on those ordinary algebra systems (on a system with 11Gi of ram).++## Get Started++1. Run `make`. This will build via stack and also copy the `subs` executable to `build/subs`.+2. Place `subs` to within your path.+3. You are ready to use `subs`.++## Help Doc++```+$ subs --help+frequent-substring help:++Usage: subs [-i|--filepath FilePath] [-l|--length INT] [-r|--repeats INT] + [-s|--substitute String] [-v|--verbose]++ find frequent subsequences in a text file++Available options:+ -i,--filepath FilePath path to input file containing the text sequence+ -l,--length INT find the most frequent subsequence of a specified+ length+ -r,--repeats INT find the longest subsequence which repeats this many+ times+ -s,--substitute String replace the subsequence found with a specified string+ -v,--verbose whether to display counts, etc.+ -h,--help Show this help text+```++## Typical Workflow++The longest-subsequence function (`-r`) uses a binary search.+A typical workflow on a long file might be to run with `-l` (and `-v`) a few times,+to get an idea of what number of repeats to specify.++```+$ subs -i res/formula -l 100 -v+Finding the most frequent subsequence of length 100 in the content of res/formula+content has length: 2500530+number of subsequences of exact length 100: 2500431+substring:+*d^2*e^2*g*h - 24*e^4*g*h + 192*c^2*g^3*h - 12*d^2*g^3*h - 60*e^2*g^3*h + 12*g^5*h - 24*c^4*h^2 - 72+length: 100+repeats: 189+```++Then use `-r` with that number of repeats, to find the longest substring that repeats at least that many times:++```+$ subs -i res/formula -r 189 > substring-that-repeats-at-least-189-times.txt+```++or, obtain the original formula but with a specified substitution applied:++```+$ subs -i res/formula -r 189 -s substituteTerm > original-with-substitution-applied.txt+```++## Examples++### Searching by length:++```+$ subs -i res/formula -l 17+*sqrt(e^2 - h^2)*+```++with verbose:++```+$ subs -i res/formula -l 17 -v+Finding the most frequent subsequence of length 17 in the content of res/formula+content has length: 13209+number of subsequences of exact length 17: 13193+substring:+*sqrt(e^2 - h^2)*+length: 17+repeats: 190+```++### Performing a substitution when searching by length:++```+$ subs -i res/formula -l 17 -s "*eMinusH*"+(16*c^6 + 24*c^4*d^2 + 12*c^2*d^4 + 2*d^6 - 24*c^4*e^2 + 24*c^2*d^2*e^2 + 18*d^4*e^2 + 12*c^2*e^4 - 18*d^2*e^4 - 2*e^6 - 84*c^4*g^2 - 30*c^2*d^2*g^2 + 6*d^4*g^2 + 66*c^2*e^2*g^2 - 42*d^2*e^2*g^2 - 12*e^4*g^2 + 66*c^2*g^4 + 6*d^2*g^4 + 12*e^2*g^4 + 2*g^6 - 96*c^4*g*h - 96*c^2*d^2*g*h - 24*d^4*g*h + 96*c^2*e^2*g*h - 48*d^2*e^2*g*h - 24*e^4*g*h + 192*c^2*g^3*h - 12*d^2*g^3*h - 60*e^2*g^3*h + 12*g^5*h - 24*c^4*h^2 - 72*c^2*d^2*h^2 - 30*d^4*h^2 + 24*c^2*e^2*h^2 + 12*d^2*e^2*h^2 - 6*e^4*h^2 + 222*c^2*g^2*h^2 + 132*d^2*g^2*h^2 - 102*e^2*g^2*h^2 - 54*g^4*h^2 + 96*c^2*g*h^3 + 144*d^2*g*h^3 - 48*e^2*g*h^3 - 116*g^3*h^3 + 12*c^2*h^4 + 30*d^2*h^4 - 6*e^2*h^4 - 90*g^2*h^4 - 24*g*h^5 - 2*h^6 + 48*eMinusH*c^4*d + 48*eMinusH*c^2*d^3 + 12*eMinusH*d^5 - 156*eMinusH*c^2*d*e^2 + 120*eMinusH*d^3*e^2 ++...+```++### Searching by number of repeats:++```+$ subs -i res/formula -r 150+*sqrt(e^2 - h^2)*+```++with verbose:++```+$ subs -i res/formula -r 150 -v+Finding the longest subsequence that repeats 150 times, in the content of res/formula+content has length: 13209+number of subsequences with length at least 0: 87258655+substring:+*sqrt(e^2 - h^2)*+length: 17+repeats: 190+```++### Performing a substitution when searching by number of repeats:++```+$ subs -i res/formula -r 150 -s "*eMinusH*"+(16*c^6 + 24*c^4*d^2 + 12*c^2*d^4 + 2*d^6 - 24*c^4*e^2 + 24*c^2*d^2*e^2 + 18*d^4*e^2 + 12*c^2*e^4 - 18*d^2*e^4 - 2*e^6 - 84*c^4*g^2 - 30*c^2*d^2*g^2 + 6*d^4*g^2 + 66*c^2*e^2*g^2 - 42*d^2*e^2*g^2 - 12*e^4*g^2 + 66*c^2*g^4 + 6*d^2*g^4 + 12*e^2*g^4 + 2*g^6 - 96*c^4*g*h - 96*c^2*d^2*g*h - 24*d^4*g*h + 96*c^2*e^2*g*h - 48*d^2*e^2*g*h - 24*e^4*g*h + 192*c^2*g^3*h - 12*d^2*g^3*h - 60*e^2*g^3*h + 12*g^5*h - 24*c^4*h^2 - 72*c^2*d^2*h^2 - 30*d^4*h^2 + 24*c^2*e^2*h^2 + 12*d^2*e^2*h^2 - 6*e^4*h^2 + 222*c^2*g^2*h^2 + 132*d^2*g^2*h^2 - 102*e^2*g^2*h^2 - 54*g^4*h^2 + 96*c^2*g*h^3 + 144*d^2*g*h^3 - 48*e^2*g*h^3 - 116*g^3*h^3 + 12*c^2*h^4 + 30*d^2*h^4 - 6*e^2*h^4 - 90*g^2*h^4 - 24*g*h^5 - 2*h^6 + 48*eMinusH*c^4*d + 48*eMinusH*c^2*d^3 + 12*eMinusH*d^5 - 156*eMinusH*c^2*d*e^2 + 120*eMinusH*d^3*e^2 ++```++### Reading from standard input:++```+$ cat res/formula | subs -l 17+*sqrt(e^2 - h^2)*+```++```+$ cat res/formula | subs -r 150+*sqrt(e^2 - h^2)*+```++++
+ app/Main.hs view
@@ -0,0 +1,185 @@+{-# LANGUAGE OverloadedStrings #-}+module Main (main) where++import Prelude hiding (readFile, putStrLn, length, getContents)+import FrequentSubstring ( mostFrequentSubstringN+ , countSubsequencesWithLengthAtLeast+ , countSubsequencesOfLength+ , longestSubstringWithRRepeats+ )+import Options.Applicative+import Data.Text.IO (readFile, putStrLn, getContents)+import Data.Text as T (Text, pack)+import qualified Data.Text as T (length)+import Data.Text.Lazy (fromStrict, toStrict)+import Util (showText)+import Text.Replace (Replace(Replace), replaceWithList, text'fromText)++data Options = Options+ (Maybe FilePath) -- inputPath+ (Maybe Int) -- length; used to find the most frequent subsequence of the specified length+ (Maybe Int) -- repeats; used to find the longest subsequence which repeats this many times+ (Maybe String) -- substitute; replace the subsequence found with this+ Bool -- isVerbose++options :: Parser Options+options = Options+ <$> optional (strOption+ ( long "filepath"+ <> short 'i'+ <> metavar "FilePath"+ <> help "path to input file containing the text sequence"+ ))+ <*> optional (option auto+ ( long "length"+ <> short 'l'+ <> help "find the most frequent subsequence of a specified length"+ <> metavar "INT"+ ))+ <*> optional (option auto+ ( long "repeats"+ <> short 'r'+ <> help "find the longest subsequence which repeats this many times"+ <> metavar "INT"+ ))+ <*> optional ( strOption+ ( long "substitute"+ <> short 's'+ <> metavar "String"+ <> help "replace the subsequence found with a specified string"+ ))+ <*> switch+ ( long "verbose"+ <> short 'v'+ <> help "whether to display counts, etc."+ )++main :: IO ()+main = greet =<< execParser opts+ where opts = info (options <**> helper)+ ( fullDesc+ <> progDesc "find frequent subsequences in a text file"+ <> header "frequent-substring help:"+ )++greet :: Options -> IO ()+greet (Options _ Nothing Nothing Nothing _) = do+ putStrLn "No length nor number-of-repeats was specified; nothing to do."+greet (Options inputPathMb (Just length) Nothing Nothing isVerbose) = do+ if isVerbose then do+ putStrLn $ "Finding the most frequent subsequence of length "+ <> showText length <> " in the content of "+ <> nameInputSource inputPathMb+ else return ()+ content <- getSequence inputPathMb+ if isVerbose then do+ let contentLength = T.length content+ putStrLn $ "content has length: " <> showText contentLength+ putStrLn $ "number of subsequences of exact length " <> showText length <> ": "+ <> showText (countSubsequencesOfLength contentLength length)+ else return ()+ let (substring,count) = mostFrequentSubstringN length content+ if isVerbose then do+ putStrLn "substring:"+ putStrLn substring+ putStrLn $ "length: " <> showText (T.length substring)+ putStrLn $ "repeats: " <> showText count+ else do+ putStrLn substring+greet (Options inputPathMb Nothing (Just repeats) Nothing isVerbose) = do+ if isVerbose then do+ putStrLn $ "Finding the longest subsequence that repeats "+ <> showText repeats+ <> " times, in the content of "+ <> nameInputSource inputPathMb+ else return ()+ content <- getSequence inputPathMb+ if isVerbose then do+ let contentLength = T.length content+ putStrLn $ "content has length: " <> showText contentLength+ putStrLn $ "number of subsequences with length at least " <> showText (0::Int) <> ": "+ <> showText (countSubsequencesWithLengthAtLeast contentLength 0)+ else return ()+ let (substring, count) = longestSubstringWithRRepeats repeats content+ if isVerbose then do+ putStrLn "substring:"+ putStrLn substring+ putStrLn $ "length: " <> showText (T.length substring)+ putStrLn $ "repeats: " <> showText count+ else do+ putStrLn substring+greet (Options _ Nothing Nothing (Just _) _) = do+ putStrLn "No length nor number-of-repeats was specified; nothing to do."+greet (Options _ (Just _) (Just _) Nothing _) = do+ putStrLn "Both length and number-of-repeats was specified; this functionality does not yet exit."+greet (Options inputPathMb (Just length) Nothing (Just substitute) isVerbose) = do+ if isVerbose then do+ putStrLn $ "Finding the most frequent subsequence of length "+ <> showText length <> " in the content of "+ <> nameInputSource inputPathMb+ else return ()+ content <- getSequence inputPathMb+ if isVerbose then do+ let contentLength = T.length content+ putStrLn $ "content has length: " <> showText contentLength+ putStrLn $ "number of subsequences of exact length " <> showText length <> ": "+ <> showText (countSubsequencesOfLength contentLength length)+ else return ()+ let (substring,count) = mostFrequentSubstringN length content+ let replaced = substituteText content substring (pack substitute)+ if isVerbose then do+ putStrLn "substring:"+ putStrLn substring+ putStrLn $ "length: " <> showText (T.length substring)+ putStrLn $ "repeats: " <> showText count+ putStrLn "substitute:" + putStrLn (pack substitute)+ putStrLn $ "content of " <> nameInputSource inputPathMb <> " after replacement:"+ putStrLn replaced+ else do+ putStrLn replaced+greet (Options inputPathMb Nothing (Just repeats) (Just substitute) isVerbose) = do+ if isVerbose then do+ putStrLn $ "Finding the longest subsequence that repeats "+ <> showText repeats+ <> " times, in the content of "+ <> nameInputSource inputPathMb+ else return ()+ content <- getSequence inputPathMb+ if isVerbose then do+ let contentLength = T.length content+ putStrLn $ "content has length: " <> showText contentLength+ putStrLn $ "number of subsequences with length at least " <> showText (0::Int) <> ": "+ <> showText (countSubsequencesWithLengthAtLeast contentLength 0)+ else return ()+ let (substring, count) = longestSubstringWithRRepeats repeats content+ let replaced = substituteText content substring (pack substitute)+ if isVerbose then do+ putStrLn "substring:"+ putStrLn substring+ putStrLn $ "length: " <> showText (T.length substring)+ putStrLn $ "repeats: " <> showText count+ putStrLn "substitute:" + putStrLn (pack substitute)+ putStrLn $ "content of " <> nameInputSource inputPathMb <> " after replacement:"+ putStrLn replaced+ else do+ putStrLn replaced+greet (Options _ (Just _) (Just _) (Just _) _) = do+ putStrLn "Both length and number-of-repeats was specified; this functionality does not yet exit."++nameInputSource :: Maybe String -> Text+nameInputSource Nothing = "the piped input"+nameInputSource (Just inputPath) = pack inputPath++-- | If Nothing, reads from stdin.+-- | Otherwise, read from the filepath in the Just.+getSequence :: Maybe String -> IO Text+getSequence Nothing = getContents+getSequence (Just inputPath) = readFile inputPath++substituteText :: Text -> Text -> Text -> Text+substituteText content substring substitute+ = toStrict $ replaceWithList [Replace (text'fromText substring) substitute] (fromStrict content)++
+ frequent-substring.cabal view
@@ -0,0 +1,89 @@+cabal-version: 2.2++-- This file has been generated from package.yaml by hpack version 0.36.0.+--+-- see: https://github.com/sol/hpack++name: frequent-substring+version: 0.1.0.0+synopsis: Identifies and replaces frequent subsequences in long strings+description: Please see the README on GitHub at <https://github.com/mherzl/frequent-substring#readme>+category: CLI Tool+homepage: https://github.com/mherzl/frequent-substring#readme+bug-reports: https://github.com/mherzl/frequent-substring/issues+author: Matthew Herzl+maintainer: matthew@herzl.email+copyright: 2025 Matthew Herzl+license: BSD-3-Clause+license-file: LICENSE+build-type: Simple+extra-source-files:+ README.md+ CHANGELOG.md++source-repository head+ type: git+ location: https://github.com/mherzl/frequent-substring++library+ exposed-modules:+ FreqMap+ FrequentSubstring+ Util+ other-modules:+ Paths_frequent_substring+ autogen-modules:+ Paths_frequent_substring+ hs-source-dirs:+ src+ ghc-options: -Wall -Wcompat -Widentities -Wincomplete-record-updates -Wincomplete-uni-patterns -Wmissing-export-lists -Wmissing-home-modules -Wpartial-fields -Wredundant-constraints+ build-depends:+ HUnit >=1.6.2.0 && <1.7+ , base >=4.7 && <5+ , containers >=0.6.7 && <0.7+ , hashable >=1.4.3.0 && <1.5+ , optparse-applicative >=0.17.1.0 && <0.18+ , text >=2.0.2 && <2.1+ , text-replace >=0.1.0.3 && <0.2+ default-language: Haskell2010++executable frequent-substring-exe+ main-is: Main.hs+ other-modules:+ Paths_frequent_substring+ autogen-modules:+ Paths_frequent_substring+ hs-source-dirs:+ app+ ghc-options: -Wall -Wcompat -Widentities -Wincomplete-record-updates -Wincomplete-uni-patterns -Wmissing-export-lists -Wmissing-home-modules -Wpartial-fields -Wredundant-constraints -threaded -rtsopts -with-rtsopts=-N+ build-depends:+ HUnit >=1.6.2.0 && <1.7+ , base >=4.7 && <5+ , containers >=0.6.7 && <0.7+ , frequent-substring+ , hashable >=1.4.3.0 && <1.5+ , optparse-applicative >=0.17.1.0 && <0.18+ , text >=2.0.2 && <2.1+ , text-replace >=0.1.0.3 && <0.2+ default-language: Haskell2010++test-suite frequent-substring-test+ type: exitcode-stdio-1.0+ main-is: Spec.hs+ other-modules:+ Paths_frequent_substring+ autogen-modules:+ Paths_frequent_substring+ hs-source-dirs:+ test+ ghc-options: -Wall -Wcompat -Widentities -Wincomplete-record-updates -Wincomplete-uni-patterns -Wmissing-export-lists -Wmissing-home-modules -Wpartial-fields -Wredundant-constraints -threaded -rtsopts -with-rtsopts=-N+ build-depends:+ HUnit >=1.6.2.0 && <1.7+ , base >=4.7 && <5+ , containers >=0.6.7 && <0.7+ , frequent-substring+ , hashable >=1.4.3.0 && <1.5+ , optparse-applicative >=0.17.1.0 && <0.18+ , text >=2.0.2 && <2.1+ , text-replace >=0.1.0.3 && <0.2+ default-language: Haskell2010
+ src/FreqMap.hs view
@@ -0,0 +1,42 @@+module FreqMap+ ( mostFrequentInList+ ) where++import Data.List (foldl')+import Data.IntMap (IntMap, insertWith, foldlWithKey')+import qualified Data.IntMap as IM (empty)++newtype FreqMap = FreqMap (IntMap Count)+ deriving (Show)+type Key = Int+type Count = Int++-- ===========================+-- | Queries+-- ~~~~~~~~~~~~++mostFrequentInList :: [Key] -> (Key, Count)+mostFrequentInList = mostFrequent . fromList++mostFrequent :: FreqMap -> (Key, Count)+mostFrequent (FreqMap m) = foldlWithKey' accum (0,0) m+ where accum :: (Key, Count) -> Key -> Count -> (Key, Count)+ accum acc@(_, ac) k c+ | c > ac = (k,c)+ | otherwise = acc++-- ===========================+-- | Construct+-- ~~~~~~~~~~~~++fromList :: [Key] -> FreqMap+fromList l = foldl' insert empty l++insert :: FreqMap -> Key -> FreqMap+insert (FreqMap m) n = FreqMap $ insertWith (+) n 1 m++empty :: FreqMap+empty = FreqMap IM.empty++-- ===========================+
+ src/FrequentSubstring.hs view
@@ -0,0 +1,100 @@+module FrequentSubstring+ ( longestSubstringWithRRepeats+ , mostFrequentSubstringN+ , mostFrequentSubstringHashN+ , substringsLengthN+ , countSubsequencesWithLengthAtLeast+ , countSubsequencesOfLength+ ) where++import FreqMap (mostFrequentInList)++import Prelude hiding (drop, length)+import Data.Text (chunksOf, Text, drop, length, singleton, index)+import Data.Hashable (hash)+import Data.Maybe (fromMaybe)++type Hash = Int+type Count = Int++-- ===========================+-- | Find Longest by Repeats+-- ~~~~~~~~~~~~++-- | Precondition: r must be in the interval [1, length t]+longestSubstringWithRRepeats :: Int -> Text -> (Text, Count)+longestSubstringWithRRepeats r t+ | r < 1 = error "longestSubstringWithRRepeats; r cannot be less than 1"+ | r > lt = error "longestSubstringWithRRepeats; r cannot exceed (length t)"+ | otherwise = longestSubstringWithRRepeatsInternal r t upperBound lowerBound+ where lt = length t+ upperBound = (lt, t, 1 ) -- this is meant to be the same as mostFrequentSubstringN lt t+ lowerBound = (1 , singleton (index t 0), lt) -- this is meant to be the same as mostFrequentSubstringN 1 t++type Length = Int+type Repeats = Int+type Bound = (Length, Text, Repeats)+-- | Identifies the longest substring with at least R repeats.+-- | UpperBound and LowerBound correspond to existing subsequences of t, and+-- | their lengths bound the answer's length. That is:+-- | Precondition: upper-bound-length >= answer's length, and+-- | lower-bound-length <= answer's length.+longestSubstringWithRRepeatsInternal :: Int -> Text -> Bound -> Bound -> (Text, Count)+longestSubstringWithRRepeatsInternal r t u@(ul,ut,ur) l@(ll,_,_)+ | ur==r = (ut,ur)+ | gl==ll = (gt,gr)+ | gr >= r = longestSubstringWithRRepeatsInternal r t u g+ | gr < r = longestSubstringWithRRepeatsInternal r t g l+ | otherwise = error "longestSubstringWithRRepeatsInternal; all cases should have already been covered"+ where gl = (ul+ll) `div` 2+ (gt,gr) = mostFrequentSubstringN gl t+ g = (gl,gt,gr)++-- ===========================+-- | Find by Length+-- ~~~~~~~~~~~~++-- | Most frequent substring of length n+mostFrequentSubstringN :: Int -> Text -> (Text, Count)+mostFrequentSubstringN n t = (s, count)+ where substrings :: [Text]+ substrings = substringsLengthN n t+ hashSubstringAssList :: [(Int, Text)]+ hashSubstringAssList = ((,) =<< hash) <$> substrings+ (h, count) = mostFrequentInList $ fst <$> hashSubstringAssList+ s = fromMaybe err $ lookup h hashSubstringAssList+ err = error $ "mostFrequentSubstringLengthN; no substrings of length " ++ show n++mostFrequentSubstringHashN :: Int -> Text -> (Hash, Count)+mostFrequentSubstringHashN n t = mostFrequentInList hashes+ where hashes = hash <$> substringsLengthN n t++substringsLengthN :: Int -> Text -> [Text]+substringsLengthN n t = chunksLengthN n `concatMap` suffixes+ where suffixes = (flip drop) t <$> [0..n-1]++chunksLengthN :: Int -> Text -> [Text]+chunksLengthN n t = filter ((n<=) . length) $ chunksOf n t++-- ===========================+-- | Count+-- ~~~~~~~~~~~~++countSubsequencesWithLengthAtLeast :: Int -> Int -> Int+countSubsequencesWithLengthAtLeast sequenceLength threshold+ | sequenceLength < 0 = 0+ | threshold < 0 = countSubsequencesWithLengthAtLeast sequenceLength 0+ | otherwise = ((st+1) * st) `div` 2+ where st = (sequenceLength - threshold + 1)++countSubsequencesOfLength :: Int -> Int -> Int+countSubsequencesOfLength sequenceLength n+ | sequenceLength < 0 = 0+ | n < 0 = 0+ | n > sequenceLength = 0+ | n==0 = 1+ | otherwise = sequenceLength - n + 1++-- ===========================++
+ src/Util.hs view
@@ -0,0 +1,9 @@+module Util+ ( showText+ ) where++import Data.Text (pack, Text)++showText :: (Show a) => a -> Text+showText = pack . show+
+ test/Spec.hs view
@@ -0,0 +1,44 @@+{-# LANGUAGE OverloadedStrings #-}++import FrequentSubstring+import Util (showText)++import Data.Text+import Test.HUnit++main :: IO Counts+main = runTestTT tests++tests :: Test+tests = TestList+ [ TestLabel "test1" test1+ , TestLabel "test2" test2+ , TestLabel "test3" test3+ ]++test3 :: Test+test3 = TestCase $ do+ let t = "aababcabcdabcdeabcdefabcdefgabcdefgh"+ let expected = ("abcd", 5)+ let r = 5+ let actual = longestSubstringWithRRepeats r t+ assertEqual (unpack $ "longestSubstringWithRRepeats r=" <> showText r) expected actual++test2 :: Test+test2 = TestCase $ do+ let t = "abbcccddddeeeeeffffffggggggghhhhhhhh"+ let expected = ("hhhhh", 4)+ let r = 4+ let actual = longestSubstringWithRRepeats r t+ assertEqual (unpack $ "longestSubstringWithRRepeats r=" <> showText r) expected actual++test1 :: Test+test1 = TestCase $ do+ let t = "abbcccddddeeeeeffffffggggggghhhhhhhh"+ let expected = ("h", 8)+ let r = 8+ let actual = longestSubstringWithRRepeats r t+ assertEqual (unpack $ "longestSubstringWithRRepeats r=" <> showText r) expected actual+++