Interviewstreet Challenge: String Similarity

Problem

https://www.interviewstreet.com/challenges/dashboard/#problem/4edb8abd7cacd

String Similarity (25 Points)

For two strings A and B, we define the similarity of the strings to be the length of the longest prefix common to both strings. For example, the similarity of strings "abc" and "abd" is 2, while the similarity of strings "aaa" and "aaab" is 3.

Calculate the sum of similarities of a string S with each of it's suffixes.

Input:
The first line contains the number of test cases T. Each of the next T lines contains a string each.

Output:
Output T lines containing the answer for the corresponding test case.

Constraints:
1 <= T <= 10
The length of each string is at most 100000 and contains only lower case characters.

Sample Input:
2
ababaa
aa

Analysis

All Java Solutions on the InterviewStreet needs to run in 5 seconds with 256 MB maximum RAM available. So that means our solution can never be "Brute-Force" or O(n^2). Same applies to the space complexity.

So the length of the String can be upto 1,00,000 and in total we have upto 10 test cases. All these have to be run in 5 secs. So the hint here is that you cannot do any String manipulation operations. If you are using String.indexOf or String.charAt then you would incur additional time. A better option is to convert the String to character arrray and work on it.

The next hint is that instead of creating multiple substrings, create a virtual substring inline. So what it means is, If the string is "raju", I don't need to store another substring "aju". I can use 2 pointers one pointing at string "raju" position 0 and other pointing string "raju" position 1. If they match, increment the counter and move the pointers forward.

E.g.

String "ababaa". The first substring is the original string itself "ababaa" and it would match for all characters.

Next we need to compare "ababaa" with "babaa". So check index 0 and index 1. they don't match. So stop here.

Next proceed for "ababaa" with "abaa". So check index 0 and index 2 (a and a). They match. Increment counter. Next index 1 and Index 3 (b and b). Again increment counter. Next also match. After that b does not match with a. So stop here.

Continue this search.

Solution