Data Structures Question

[BestJewSinceJC]

What would be the best way to implement dynamic search? So, for example, given the words:

the, then, behemoth, abchemto

Typing in 'he' would return all of the above words since they all have he in them. Is the best way to do this using a Trie?

[BestJewSinceJC]

We just did it with regex Patterns. How do I make this pattern so that the "ptrn" portion, which is a String the user entered, could be in lower OR uppercase? But so that this wouldn't cause errors if the user didn't enter alphabet characters?

patrnStr = ".*" + ptrn + ".*";

[~s.o.s~]

> Is the best way to do this using a Trie?
Judging by its description, it does seem to be a good way of doing things, better than regular expressions at least when used over a large data set.

A simple program to get the ball rolling:

package net.sos.playground;

import java.util.Scanner;
import java.util.regex.Matcher;
import java.util.regex.Pattern;

public class RegexTest {

   public static void main(final String[] args) {
      new RegexTest().run();
   }
   
   public void run() {
      Scanner in = new Scanner(System.in);
      String input = null, pattern = null;
      while(true) {
         System.out.print("Enter the pattern: ");
         if(in.hasNext()) {
            pattern = in.next();
         }
         System.out.print("Enter the input: ");
         if(in.hasNext()) {
            input = in.next();
         }
         if(testExistence(input, pattern)) {
            System.out.println("Match found\n");
         } else {
            System.out.println("No Match found\n");
         }
      }
   }

   private boolean testExistence(String input, String pattern) {
      pattern = Pattern.quote(pattern);
      Pattern p = Pattern.compile(pattern, Pattern.CASE_INSENSITIVE);
      Matcher matcher = p.matcher(input);
      return matcher.find();
   }

}

Pay special attention to the testExistence method. The method Pattern.quote is required to escape all the regex special characters and treat them as literals. If, for example, the user enters a `*', which happens to be a special character signifying `zero or more occurrences', your Regular object creation will fail. The Pattern.CASE_INSENSITIVE flag is required since the default regular expression matching done by the String.match method is case sensitive.

Once the Pattern object for the given pattern and the Matcher object for the given user input is created, all that remains is to test for the presence of the given pattern in the input using the Matcher.find method.

[BestJewSinceJC]

I finished my program hours ago and it works for case sensitive input. . appreciate the tip on the CASE_INSENSITIVE argument. I notice your comment, "The method Pattern.quote is required to escape all the regex special characters and treat them as literals." Why would I want to do that in this case? Or were you just mentioning it as a general tip? Because in this case, I want to match any characters found before what the user entered and any characters found afterwards.

[~s.o.s~]

Let's suppose that your program creates regex patterns based on the input provided by the user. Assuming the user enters `*' as the pattern and `hello' as the input string, the regular expression string would look like:

patrnStr = ".*" + ptrn + ".*";
patrnStr = ".**.*";

...which isn't a valid regular expression since it has a dangling meta-character, which is the *.

BTW, you can drop the ".*" present at the beginning and the end of your pattern string; they aren't required for detecting a match.

[BestJewSinceJC]

Ok, thank you, I see what you're saying now. I'm glad you mentioned that because it might have escaped testing.