What is the most efficient way to check if a string is part of a bigger string?

Question

I have a string which is formed by concatenation of IP addresses, for example:

"127.272.1.43;27.27.1.43;127.127.27.67;128.27.1.43;127.20.1.43;111.27.1.43;127.27.1.43;"

When a new IP address is given, I need to check if the first half of the IP is part of the IP address string. For example, if "127.27.123.23" is given I need to find if any of the IP address in the string starts with "127.27"

I have the following code, where userIP = "127.27."

int i = StringUtils.indexOf(dbIPString, userIP);
do {
    if (i > 0) {
        char ch = dbIPString.charAt(i - 1);
        if (ch == ';') {
            System.out.println("IP is present in db");
            break;

        } else {
            i = StringUtils.indexOf(dbIPString, userIP, i);
        }
    } else if (i == 0) {
        System.out.println("IP is present in db");
        break;
    } else {

        System.out.println("IP is not present in db");
    }
} while (i >= 0);

Can it be more efficient? Or can I use regular expression? Which one is more efficient?

Answer 1

Plain string matches are usually faster than regex matches. I'd keep it simple and do something like this:

if (StringUtils.startsWith(dbIPString, userIP)) {
    ... // prefix is present
} else if (StringUtils.indexOf(dbIPString, ";" + userIP) > 0) {
    ... // prefix is present
} else {
    ... // prefix is not present
}

If you can arrange to have the list always begin with a ';' then searching the first entry would no longer be a special case and the logic can be simplified.

If the list will be large and you're going to be doing a lot of these searches and speed really matters then perhaps you could add each prefix to some sort of hash or tree as you build the list of addresses. Lookups in those data structures should be faster than string matches.

Answer 2

Assuming that you only care for entire IP address matches, and assuming you don't want 127.255.1.43 to match when you're looking for 127.25, then

(?<=^|;)127\.25\.\d+\.\d+

would be a fitting regex.

In Java:

Pattern regex = Pattern.compile(
    "(?<=^|;)       # Assert position at the start of the string or after ;\n" +
    Pattern.quote(userIP) +
    "\\.\\d+\\.\\d+ # Match .nnn.nnn", 
    Pattern.COMMENTS);