Regex: find all possible matches

[Alessio]

Hi,

this is a problem that has been bothering me a while now:

imagine you have a string (e.g. "___a___b___c___") and you have a regex (e.g. "([abc]).*([abc])") and you want to find all possible combinations of matching groups (e.g. a-b, a-c, b-c).

You can play around with greedy and non greedy quantifiers (e.g. "([abc]).*([abc])" and "([abc]).*?([abc])") which will find some of this combinations (e.g. a-b and a-c) - but not all (in this case not b-c).

What I've been doing till now is basically this:

String haystack = "___a___b___c___";
for (int j = 0; j < 100; j++) {
	for (int i = 0; i < 100; i++) {
		String pattern = "^.{" + j + "}([abc]).{" + i + "}([abc])";
		Pattern p = Pattern.compile(pattern);
		Matcher m = p.matcher(haystack);
		while (m.find()) {
			System.out.printf("%2d,%2d : %s - %s\n",
					j, i, 
					m.group(1),
					m.group(2));
		}
	}
}

output:

 3, 3 : a - b
 3, 7 : a - c
 7, 3 : b - c

this code runs through all possible string lengths and finds all combinations that match the given pattern.

However it does this by trying all possible expressions (in this case 100*100 = 10000 times - yes you could use less than 100, but you get the point).

Is there a more elegant (i.e. faster) solution to this?

Regards,
Alessio

[Alessio]

*bump* (sorry, about that)

[Zack]

This is probably how I'd do it... it's not much "faster" but it prevents hardcoding values (like 100).

String haystack = "___a___b___c___";
for (int i = 0; i < haystack.length() - 1; i++) {
	for (int j = i + 1; j < haystack.length(); j++) {
		String pattern = "^([abc]).*([abc])$";
		Pattern p = Pattern.compile(pattern);
		Matcher m = p.matcher(haystack.substring(i,j));
		while (m.find()) {
			System.out.printf("%2d,%2d : %s - %s\n",
					i,j,
					m.group(1),
					m.group(2));
		}
	}
}

This code loops through the string starting at some point then uses all the subsets of the string after that point. Using the substring method, it pulls a section out of the string. For example, you'd get something like this for the value of haystack.substring(i,j):

_
__
___
___a
___a_
___a__
___a___
___a___b
___a___b_
...
_
_c
_c_
_c__
c
c_
c__
_
__
_

Then the regex compares that pattern (using string start/end ^$) to the substring taken out. If it matches, it records the start/end indices.

I'm kind of convinced there's a faster way to do this yet, so I'm still looking. This was worth posting I thought though.

[Alessio]

Yes, thats definitely a possibility, but basically it does the same thing as my code: just try every possible sub string / string length.

I'm beginning to think that thats just the only possible solution with the Java Regex Parser...