We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  • HackerRank Home

    HackerRank

  • |
  • Prepare
  • Certify
  • Compete
  • Apply
  • Hiring developers?
  1. Prepare
  2. Functional Programming
  3. Functional Structures
  4. Substring Searching
  5. Discussions

Substring Searching

Problem
Submissions
Leaderboard
Discussions

Sort 22 Discussions, By:

recency

Please Login in order to post a comment

  • shely7496
    4 months ago+ 0 comments

    The issue in Haskell is effectively making the table. This should be O(N) yet relies upon table queries being O(1), which they aren't utilizing records or even arrangements. In the end I concluded that one needed to go external the soul of Haskell, and seemingly utilitarian programming, and utilize a changeable cluster. check here

    0|
    Permalink
  • __alexey__
    9 months ago+ 0 comments

    Scala solution works with prefix function as ArrayBuffer.

    Description of pseudocode for the table-building algorithm in the Wikipedia link is not correct.

    Correct algorithm can be found here https://cp-algorithms.com/string/prefix-function.html#implementation

    vector<int> prefix_function(string s) {
        int n = (int)s.length();
        vector<int> pi(n);
        for (int i = 1; i < n; i++) {
            int j = pi[i-1];
            while (j > 0 && s[i] != s[j])
                j = pi[j-1];
            if (s[i] == s[j])
                j++;
            pi[i] = j;
        }
        return pi;
    }
    
    0|
    Permalink
  • andrey1981spb
    1 year ago+ 0 comments

    Solution on Scala. It is based on Map ("indexedMap"). In which key is a char, which is present such in word and pat-candidate. And value is list of char order indexes. Each index is consistently incremented, when character of pat is found in word. For example, word "videobox" for pat "videobox" represented as ("v"->List(0), "i"->List(1),"d"->List(2),"e"->List(3),"0"->List(4,6),"b"->List(5),"x"->List(7)). Using this map, consistently compare indexes of pat-candidate with indexes of word in order to find the order. Order is detected, where the difference between indexes equals one (for example 6 and 5). If an order is detected for all characters in pat-candidate, pat is confirmed.

    `case class T(text: String, pat: String)
    
    class Solution {
    
     def findPats(casesNumber: Int, cases: List[T]) = {
    
    def findPat(testCase: T) = {
      def findOrder(curIndList: List[Int], prevIndList: List[Int]): Boolean = {
        val rez = for {
          c<-curIndList
          p<-prevIndList
          if (p - c == 1) || (c - p == 1)
        } yield c
      rez.nonEmpty
      }
    
      @tailrec
      def indexedMap(text: List[Char], cMap: Map[Char, List[Int]], index: Int): Map[Char, List[Int]] = text match {
        case c::_ if cMap.contains(c) && text.nonEmpty =>
          val updatedMap = cMap + (c -> cMap(c).::(index + 1))
          indexedMap(text.tail, updatedMap, index + 1)
        case c::_ if !cMap.contains(c) && text.nonEmpty =>
          val updatedMap = cMap + (c -> List((index + 1)))
          indexedMap(text.tail, updatedMap, index + 1)
        case _ => cMap
      }
    
      val textMap = indexedMap(testCase.text.toList, Map.empty[Char, List[Int]], -1)
      val firstOcc = List(textMap.getOrElse(testCase.pat.head, List(0)))
      val rez = testCase.pat.foldLeft((List(testCase.pat.head), firstOcc)) {
        (acc, el) => {
          val curIndList = textMap.getOrElse(el, List(0))
          val append = if (acc == firstOcc || findOrder(curIndList, acc._2.last)) (acc._1:+el, acc._2:+curIndList) else acc
          append
        }
      }._1
      if (rez.length == testCase.pat.length) println("YES") else println("NO")
    }
    
    cases.foreach(findPat)
     }
    }`
    
    0|
    Permalink
  • krohitpatil15
    2 years ago+ 0 comments

    java code

    0|
    Permalink
  • fpq07040
    3 years ago+ 0 comments

    11/15

    pack :: [a] -> [(a,a)]
    pack [] = []
    pack [x] = []
    pack (x:y:xs) = (x,y) : pack xs
    
    f :: Eq a => [a] -> [a] -> Bool
    f xs ys = acc xs ys (length ys) where
        acc [] [] _ = True
        acc xs ys n | length xs < n = False
                    | otherwise = if take n xs == ys then True else acc (tail xs) ys n
    
    
    showRes :: Bool -> String
    showRes True = "YES"
    showRes _ = "NO"
    
    main :: IO()
    main = do
        _ <- getLine
        inp <- getContents
        mapM_ putStrLn $ map showRes $ map (uncurry f) $ pack $ lines inp
    
    0|
    Permalink
Load more conversations

Need Help?


View top submissions
  • Blog
  • Scoring
  • Environment
  • FAQ
  • About Us
  • Support
  • Careers
  • Terms Of Service
  • Privacy Policy