detecting first sequence in an array

given 开发者_Go百科a string say "4 2 5 5 5 1 5 5 5 29 8", I would like to write a function that returns the first repeating longest sequence of numbers. In this case it would return 555. What is the best and most efficient way to do this?

this is not a homework, it's one of the programming challenge that I encountered

UPDATE My initial approach is to use the convert this into an array of chars, traverse the array, and use the indexOf to see if there is another number say 5 in this array of chars, if there is then I check the next index of 5 if it is the same.. I hope this makes sense.. but this just doesn't work for the example above

---

Please have a look on suffix tree http://en.wikipedia.org/wiki/Longest_repeated_substring_problem. One could use Ukkonen online algorithm to build a tree in a O(n) time [as far as i remember]. So while building a tree you could mark the longest repeating substring.

Suffix Trees are very useful today. :) Hope my anwser will help you.

Cheers, Rafa

---

However I found something which is similar to these problems,

Longest Increasing Subsequence

http://en.wikipedia.org/wiki/Longest_increasing_subsequence

and

Longest Decreasing Subsequence

Your problem seems like falling under this category. Check the link above it has a psuedo code to solve this type of mathematical problem.

The largest clique in a permutation graph is defined by the longest decreasing subsequence of the permutation that defines the graph; the longest decreasing subsequence is equivalent in computational complexity, by negation of all numbers, to the longest increasing subsequence. Therefore, longest increasing subsequence algorithms can be used to solve the clique problem efficiently in permutation graphs.

Code something up, an than you may update us...Hopefully you will nail it!

Good Luck!

---

That seems like an extremely strange question, because that's trivial. The following code snippet returns the starting point of the first sequence it finds or -1 if there's none. Since we don't care about the longest sequence we basically just have to search for 2 consecutive values:

for (int i = 0; i < arr.length - 1; i++) 
    if (arr[i] == arr[i+1]) return i;
return -1

That's O(N) and you can't do better for an arbitrary array without some pre computation. But I assume you forgot some part of the problem?

---

Using dynamic programming this can be solved in quadratic time (a naive approach would be in O(n³)).

def s(t):
    n = len(t)
    ss = [[0 for i in range(n+1)] for j in range(n+1)]
    maximum = 0
    max_end = 0
    for i in range(n):
        for j in range(i+1, n):
            ss[i+1][j+1] = ss[i][j] + 1 if t[i] == t[j] else 0
        tmp = max(ss[i+1])
        if tmp > maximum:
            max_end, maximum = i+1, tmp
    return t[max_end-maximum:max_end]

And for your example:

>>> s("4 2 5 5 5 1 5 5 5 29 8".split(" "))
['5', '5', '5']

Depending on the context though, a suffix tree might be quicker (probably up to O(n∙log n)).

---

I assume you want the first of the longest sequences (i.e. the longest sequence, if there are several, then the fist).

This can be done in a single pass (thus O(n)):

In java-like pseudocode (on integers):

int[] firstLongest(int[] list) {
    if (list.length <= 1) return list;

    int maxLen = 1;  // length of the max sequence
    int maxEnd = 0;  // last item for the max sequence

    int curLen = 1; // length of the current sequence

    for (int i = 1; i < aList.length; i++) {
        if (list[i] == list[i-1]) {
            curLen++;
        }
        else {
            curLen = 1;
        }
        if (curLen > maxLen) {maxLen = curLen; maxEnd = i;}
    }

    return list.subList(maxEnd-maxLen+1, maxEnd+1);
}