Win a copy of Design for the Mind this week in the Design forum!
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic

how greedy quantifier works

 
Ravi Bansal
Ranch Hand
Posts: 86
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
The below program giving me the output as

0
1
2
5
6
8

I want to understand how does greedy quantifier works(i did not understand the above output) as far as i know it scans the entire source and then reads backwards and finds the rightmost match?

Regex x* should give me the index of patterns matching with zero or more occurences of x in the source string yyxxxyxx. The source string has length 8 and its 0 based index . How come i m seeing 8 in the output if the last character in the source has 7 index?

import java.util.regex.*;


public class myClass {

public static void main(String s[]){
Pattern p=Pattern.compile("x*");
Matcher m=p.matcher("yyxxxyxx");
boolean b=false;
while (b=m.find())
{
System.out.println(m.start());
}

}
}
 
Steven Landers
Ranch Hand
Posts: 30
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
x* means "0 or more x characters"

So when searching through yyxxxyxx...

- at the first y, it finds 0 x's - a match is found at index 0.
- at the second y, it finds 0 x's - a match is found at index 1.
- at the first x, it finds 3 x's - a match is found at index 2.
...(other 2 x's already part of a match in previous find)...
- at the third y, it finds 0 x's - match is found at index 5
- at the fourth x, it finds 2 x's - match is found at index 6
...(other 1 x is already part of a match in previous find)...
- at the end of the string it finds 0 x's - a match is found at index 8

The last one is the most difficult to understand. Think of it as a hidden 'end character' of a string considered in a match.find(). The key to this is we are searching for "0 or more" - and that when a match is found, it is removed from consideration.
 
Brian Legg
Ranch Hand
Posts: 488
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Good explanation, I didn't understand the greedy quantifier either.
 
marc weber
Sheriff
Posts: 11343
Java Mac Safari
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
For further reading, see Regex Tutorial - Quantifiers.
 
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic