3 Replies Latest reply: Dec 14, 2009 7:57 PM by 843853 RSS

    String matching algorithm

    843853
      Hi,

      I just read a bit about different string matching algorithms and checked out the implementation of Sun's String.indexOf(). I noticed they implemented the so called 'naive way' instead of, usually, much faster algorithms like the Boyer/Moore one. What reason might behind this implementation decision?

      Regards,
      Stefan
        • 1. Re: String matching algorithm
          jwenting
          Simplicity.
          It works, it's good enough, no need to complicate matters further.

          Java is a production level language, not some academic study project where all that matters is whether it is "fancy" enough.
          • 2. Re: String matching algorithm
            843853
            I just read a bit about different string matching algorithms and checked out the implementation of Sun's String.indexOf(). I noticed they implemented the so called 'naive way' instead of, usually, much faster algorithms like the Boyer/Moore one. What reason might behind this implementation decision?
            How can you be sure that Boyer-Moore is faster? Is Boyer-Moore faster when the key is one character and the string being searched is 200 characters? If your implementation needs Boyer-Moore, you can always implement your own FastSearchString class that uses Boyer-Moore.
            • 3. Re: String matching algorithm
              843853
              Boyer-Moore algorithm requires to compute the shift-tables of the searched string, it is not necessarily faster in all cases.

              I would bet that java.util.regex.Pattern implementation actually uses BM when it applies.