time complexity of regular expression in java

Question

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

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-
– chrylis -cautiouslyoptimistic-, Commented Nov 30, 2016 at 19:52
You need to find out how matcher.find() works. How does it search a string and when does it stop. — SedJ601
– SedJ601, Commented Nov 30, 2016 at 19:52
I am going to take a wild guess and say it's equal to the complexity of matcher.find() — SedJ601
– SedJ601, Commented Nov 30, 2016 at 19:54
Possible duplicate of What is the complexity of regular expression? — k5_
– k5_, Commented Nov 30, 2016 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
– markspace, Commented Nov 30, 2016 at 20:26

k5_ · Accepted Answer · 2016-11-30 20:18:28Z

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.

answered Nov 30, 2016 at 20:18

k5_

5,6782 gold badges21 silver badges27 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

time complexity of regular expression in java

1 Answer 1

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related