Brute force string matching in Scala

Question

I'm new to Scala and for practice I'm trying to write brute-force string matching function that can return a list of indices of matches. The best that I have is pasted below. I would appreciate assitance in making this idiomatic. Also as you'll notice this just prints the indices, whereas I'd prefer a List or Stream.

def strMatching(txt: String, pat: String): Unit = {
        val N = txt.length
        val M = pat.length
        for (i <- 1 to N-M) {
            var j = 0
            while (j < M && pat(j) == txt(i+j)) {
                if (j == M-1) print(s"${i+1} ")
                j = j + 1
            }
        }
    }

Thanks a lot!

Didier Dupont · Accepted Answer · 2013-11-30 09:53:11Z

3

A possible one liner, with the brute force algorithm, could be

txt.indices.filter(i => txt.substring(i).startsWith(pat))

answered Nov 30, 2013 at 9:53

Didier Dupont

29.6k7 gold badges73 silver badges90 bronze badges

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

1 Comment

Yann Moisan Over a year ago

even shorter : txt.indices filter (txt.startsWith(pat, _))

Shyamendra Solanki · Accepted Answer · 2013-11-30 09:52:59Z

1

def strMatch(txt: String, pat: String): List[Int] = {

     var index = 0;
     var indices = List.empty[Int]

     // sliding gives a sliding window of given length
     txt sliding pat.length foreach { x => 
                                      if (pat == x) indices = indices :+ index
                                      index += 1 }

     indices
}

answered Nov 30, 2013 at 9:52

Shyamendra Solanki

8,8512 gold badges33 silver badges25 bronze badges

2 Comments

Prakhar Over a year ago

Thanks for your answer. To be honest, I'd prefer a solution that doesn't use a var

Shyamendra Solanki Over a year ago

It's fine. The above function with var is side-effect free, which is what matters.

Collectives™ on Stack Overflow

Brute force string matching in Scala

2 Answers 2

1 Comment

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

1 Comment

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related