little problem on code for finding substring within string scala

Question

I am currently working on a small code that should allow to tell if a given substring is within a string. I checked all the other similar questions but everybody is using predefined functions. I need to build it from scratch… could you please tell me what I did wrong?

def substring(s: String, t: String): Boolean ={
 var i = 0 // position on substring
 var j = 0 // position on string
 var result = false
 var isSim = true
 var n = s.length // small string size
 var m = t.length // BIG string size


// m must always be bigger than n + j
while (m>n+j && isSim == true){
// j grows with i
// stopping the loop at i<n
while (i<n && isSim == true){
  // if characters are similar
  if (s(i)==t(j)){
    // add 1 to i. So j will increase by one as well
    // this will run the loop looking for similarities. If not, exit the loop.
    i += 1
    j = i+1
    // exciting the loop if no similarity is found
  }
  // answer given if no similarity is found
  isSim = false
}
}
   // printing the output
    isSim
}

substring("moth", "ramathaaaaaaa")

substring("moth", "ramathaaaaaaa") returns false. What's the problem? — Andrey Tyukin
– Andrey Tyukin, Commented Oct 14, 2018 at 13:27
Yes, but substring("math", "ramathaaaaaaa") returns false too... — Data_Gengar
– Data_Gengar, Commented Oct 14, 2018 at 13:30
my recomendation for this type of problems, is to use a debugger. For instance, Intellij offers a very easy to use (and powerful) debugger. You should then go step by step, following your algorithm, until you see where is it doing domething wrong — pedrorijo91
– pedrorijo91, Commented Oct 14, 2018 at 13:32
No, I am not Using any algorithm. By the way I cleaned all my errors, thanks for the advice on Intellij. — Data_Gengar
– Data_Gengar, Commented Oct 14, 2018 at 13:37

Andrey Tyukin · Accepted Answer · 2018-10-14 18:41:52Z

2

The problem consists of two subproblems of same kind. You have to check whether

there exists a start index j such that
for all i <- 0 until n it holds that substring(i) == string(j + i)

Whenever you have to check whether some predicate holds for some / for all elements of a sequence, it can be quite handy if you can short-circuit and exit early by using the return keyword. Therefore, I'd suggest to eliminate all variables and while-loops, and use a nested method instead:

def substring(s: String, t: String): Boolean ={
  val n = s.length // small string size
  val m = t.length // BIG string size

  def substringStartingAt(startIndex: Int): Boolean = {
    for (i <- 0 until n) {
      if (s(i) != t(startIndex + i)) return false
    }
    true
  }

  for (possibleStartIndex <- 0 to m - n) {
    if (substringStartingAt(possibleStartIndex)) return true
  }

  false
}

The inner method checks whether all s(j + i) == t(i) for a given j. The outer for-loop checks whether there exists a suitable offset j.

Example:

for (
  (sub, str) <- List(
    ("moth", "ramathaaaaaaa"),
    ("moth", "ramothaaaaaaa"),
    ("moth", "mothraaaaaaaa"),
    ("moth", "raaaaaaaamoth"),
    ("moth", "mmoth"),
    ("moth", "moth"),
  )
) {
  println(sub + " " + " " + str + ": " + substring(sub, str))
}

output:

moth  ramathaaaaaaa: false
moth  ramothaaaaaaa: true
moth  mothraaaaaaaa: true
moth  raaaaaaaamoth: true
moth  mmoth: true
moth  moth: true

If you were allowed to use built-in methods, you could of course also write

def substring(s: String, t: String): Boolean = {
  val n = s.size
  val m = t.size
  (0 to m-n).exists(j => (0 until n).forall(i => s(i) == t(j + i)))
}

edited Oct 14, 2018 at 18:41

answered Oct 14, 2018 at 13:44

Andrey Tyukin

45.1k4 gold badges65 silver badges103 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

Data_Gengar Over a year ago

Thank you very much, this really helped! I will try avoiding while loops in the future.

Andrey Tyukin Over a year ago

@Data_Gengar No, please, don't "try to avoid <insert-currently-less-fashionable-language-feature-here>". Try to understand when a language feature is useful, and when it is less useful, and why, and then try to apply it when appropriate, and don't apply it where it's not appropriate. In this particular case, if you really cared about performance, it probably wouldn't hurt to replace the function call by a while-loop, but it would be quite a hassle with indices and boolean flags.

Phasmid · Accepted Answer · 2018-10-14 19:16:57Z

0

I offer the following slightly more idiomatic Scala code, not because I think it will perform better than Andrey's code--I don't--but simply because it uses recursion and is, perhaps, slightly easier to read:

  /**
    * Method to determine if "sub" is a substring of "string".
    *
    * @param sub    the candidate substring.
    * @param string the full string.
    * @return true if "sub" is a substring of "string".
    */
  def substring(sub: String, string: String): Boolean = {
    val p = sub.toList

    /**
      * Tail-recursive method to determine if "p" is a subsequence of "s"
      *
      * @param s the super-sequence to be tested (part of the original "string").
      * @return as follows:
      *         (1) "p" longer than "s" => false;
      *         (2) "p" elements match the corresponding "s" elements (starting at the start of "s") => true
      *         (3) recursively invoke substring on "p" and the tail of "s".
      */
    @tailrec def substring(s: Seq[Char]): Boolean = p.length <= s.length && (
      s.startsWith(p) || (
        s match {
          case Nil => false
          case _ :: z => substring(z)
        }
        )
      )

    p.isEmpty || substring(string.toList)
  }

If you object to using the built-in method startsWith then we could use something like:

(p zip s forall (t => t._1==t._2))

But we have to draw the line somewhere between creating everything from scratch and using built-in functions.

edited Oct 14, 2018 at 19:16

answered Oct 14, 2018 at 18:04

Phasmid

9537 silver badges19 bronze badges

1 Comment

Data_Gengar Over a year ago

Thank you very much for your help, I'm just starting the chapter on recursive algortihms and I will soon understand this code better!

Collectives™ on Stack Overflow

little problem on code for finding substring within string scala

2 Answers 2

2 Comments

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

2 Comments

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related