Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
Suppose I have a string that goes like "abcabcdeaabcdef", where each character is either one more than the previous one or a.
If the character at position i is "c", I know that it is preceded by "ab".
I want to find the number and length of all sequences (substrings that contain sequential characters). For example, the above string would give "abc", "abcde", "a", "abcdef".
Is there a more efficient algorithm to do this than simply doing a O(n) search over the string?
You cant create an algoithm to do this in the worst case. Even if we read right to left and if we assume we can do some level of jumping (e.g if we see an f we can jump 6 spaces left) we still have to, in the worst case (the string of a's), read over the entire string. This can never be done in $o(n)$ time. The right to left with skipping will run in $O(m)$ time where $m$ is the number of increasing subsequences, and $m$ is $O(n)$.
Hmm i don't think so.Let's suppose there exists algorithm which does less then (n-2) comprehensions and gives a correct answer. (we assume we never get empty input and our input always starts with a thats why n-2)
Let's define 2 inputs A = aaaaaaa... and B = aaa....b...a.aaa
Of course f(a) = n and f(b) = n - 1 where f is our algorithm.
Let's play a game with our Alghoritm:
Let's define function g(x) = 1 if input[x] = a, 0 otherwise.
Each call to g is one comprehension. We can easily construct 2 inputs with different numer of sequences which would have identical result of n-2 calls of g
aⁿ, with no way to know without checking every character. $\endgroup$ – greybeard Jan 18 '17 at 19:50