A. You're Given a String...

The problem asks to find out such a substring that has the longest length and occurs at least two times, which is in fact equivalent to looking for two substrings (they might overlap with each other) with the longest length while they are exactly the same with each other. The solution might be simplified if one has noticed that the string consists of lower-case Lattin letters merely, i.e., a,b,...,z. The idea behind the simplification is that if two substrings are exactly the same, then their first letters must be the same as well. Thus, we can first use 26 arrays to store the positions at which each letter appears. For instance, we can assign 26 vectors (in C++ STL) for each letter, and "puch_back" the corresponding index. This can be done by traversing the string for a single time, with complexity O(N) (we use N to denote the length of string).

For each vector, we enumerate all the feasible combination of two indices (or positions), and start with these two positions and check their next one single letter at the same time. It is obvious that we will obtain two substrings and as we should keep them exactly the same, we must stop if the next one single letter of each substring is different. For instance, suppose that letter "a" has positions {1,5,7}. Then, we should check {1,5}, {1,7} and {5,7}. We adopt {1,7} as an example, i.e., we should check whether the two substrings {s[1],s[2]} and {s[7],s[8]} are the same or not. If they are the same, then we move on to check {s[1],s[2],s[3]} and {s[7],s[8],s[9]}; otherwise, we stop and store the current length. Finally, we output the maximum length as the answer.

Now, we calculate the complexity of the above solution. We denote the length of the 26 vectors as x1,x2,...,x26. For each vector, we should check xi*(xi-1)/2 combinations. For each combination, we will check at most 2N letters. Thus, the total complexity is {x1*(x1-1)/2+x2*(x2-1)/2+...+x26*(x26-1)/2}*2*N=O(N^3).