What's the complexity of Java's string split function?

Question

My string is of type"abacsdsdvvsg" or"a a a a a a a"
And I use String[] stringArray = s.split(""); or String[] stringArray = s.split(" ");
I'm wondering what would be the complexity(in O(string length)) for above splitting?
PS: I know how to calculate O(...) if code is given. Here I don't know the algorithm of split function.

Answer 1

The complexity will depend on the regex that you use to do the splitting. (Yes, the argument you supply to String.split(...) is a regex!)

For your example, it will be O(N) where N is the number of characters in the input String.

The algorithm of split is pretty straight forward, based on an existing regex implementation. A high-level description is:

1. Compile the regex and create a matcher
2. Iterate over the string:
   1. Use Matcher.find(...) to find the next word boundary
   2. Use String.substring to extract the word
   3. Add word to a list of strings
3. Convert the list of strings to an array of strings.

The searching for the breaks between "words" will be O(N) or more complex, depending on the regex (the find call). The construction of the list, result array and substrings will be O(N) in the worst case.

The precise details are in the source code, which you can find using Google. (Search for "java.lang.String" source, pick one and then drill down to the version of Java you are interested in. Or search the files in the source code ZIP file included in your JDK installation)

Answer 2

Its O(n) in your particular cases, where you're splitting by 1/0 character length separators. In general, it's O (n + k) with a k-character separator, can be implemented using the KMP algorithm. Java string split also accepts regexes as seperators, in which case its complexity depends on the matching algorithm being used. One common regex matching algorithm is the Thompson NFA algorithm.