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?

Do you want a string like `127.255.1.43` to match when looking for `127.25`? (I've chosen a more sane example than `127.272.1.43` as in your question)... — Tim Pietzcker, Apr 17 '12 at 07:39
@TimPietzcker sorry someone edited and removed the dot that followed 27.. i have added it back — Darshan N Reddy, Apr 17 '12 at 07:51

score 1 · Accepted Answer · answered Apr 17 '12 at 05:51

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.

answered Apr 17 '12 at 05:51

ottomeister

5,415
2
23
27

+1 for suggesting the use of a smarter data structure. Strings aren't meant to support fast prefix searching. If you build a tree of IP addresses, then this question becomes trivial. (I would give another +1 for suggesting the use of plain old string routines instead of regex, but I can only upvote once. ;) ) – Li-aung Yip Apr 17 '12 at 07:12
This also finds partial matches. For example if you're looking for `127.25`, it would also find `127.255.1.43` which probably is not what Darshan would expect. – Tim Pietzcker Apr 17 '12 at 07:41
@TimPietzcker nope.. because we are searching for "127.25." – Darshan N Reddy Apr 17 '12 at 07:47
@Ah, ok, the dot wasn't there when I wrote the comment. – Tim Pietzcker Apr 17 '12 at 07:53

score 0 · Answer 2 · answered Apr 17 '12 at 07:52

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);

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

2 Answers2