3

I wrote the following a java by using a regular expression to find a repeated String in the String s. Now I try to find the complexity of it, if any one know what is the complexity of it, please let me know.

           String s = "ABCABCAAAABBBBCCAAABCGABCABC";

           Pattern pattern = Pattern.compile("(?:([ABC])(?!\\1)([ABC])\\1\\2)+");
           Matcher matcher = pattern.matcher(s);

           while (matcher.find()) {
              System.out.print("FOUND");
           }
maya
  • 41
  • 1
  • 6
  • 1
    I have no idea why this is getting marked as "asking for recommendations", but it doesn't seem the OP has done much to solve the problem. – chrylis -cautiouslyoptimistic- Nov 30 '16 at 19:52
  • You need to find out how matcher.find() works. How does it search a string and when does it stop. – SedJ601 Nov 30 '16 at 19:52
  • I am going to take a wild guess and say it's equal to the complexity of matcher.find() – SedJ601 Nov 30 '16 at 19:54
  • 1
    Possible duplicate of [What is the complexity of regular expression?](http://stackoverflow.com/questions/4378455/what-is-the-complexity-of-regular-expression) – k5_ Nov 30 '16 at 20:21
  • The expression you have there looks like it tries to match up to 5 characters in a sequence, the does `+` on that, meaning one or more. This could potentially search the whole string. However it requires only one to match, so the first match should suffice. So I think it will only scan through the string once or twice, depending, so time complexity roughly equal to the number of characters in the target string `s`. – markspace Nov 30 '16 at 20:26

1 Answers1

5

Regular expressions can/are implemented by finite state machines. So statemachine with some fixed number of states and a fixed maximum number (T) of transitions between these states.

For each character a transition is taken until it is rejected or accepted.

So you have O( String.length() * T) or O( String.length() ) as T is a constant.

k5_
  • 5,450
  • 2
  • 19
  • 27