Calculating sum of similarities of strings

Puzzle:

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 its suffixes.

Explanation:

For ababaa the suffixes of the string are "ababaa", "babaa", "abaa", "baa", "aa" and "a". The similarities of each of these strings with the string "ababaa" are 6,0,3,0,1,1 respectively. Thus the answer is 6 + 0 + 3 + 0 + 1 + 1 = 11.

How can I improve execution time of this (when larger testcases are provided)?

import java.util.Scanner;
public class Solution {
public static void main(String[] args) {
Scanner scanner;
Solution sr = new Solution();
scanner = new Scanner(System.in);
int no_cases = scanner.nextInt();
for (int i = no_cases; --i >=0; ) {
String to_proc = scanner.next();
sr.solve(to_proc);
}
}
private void solve(String to_proc) {
String str=to_proc;
int len=to_proc.length();
int count=0;
int total=0;
for(int i=1;i<len;i++)
{
count=0;
for(int j=i;j<len;j++)
{
//     System.out.println(str.charAt(j)+" , "+str.charAt(j-i));
if(str.charAt(j-i)==str.charAt(j))
{
count++;
}
else
{
break;
}
}
total=total+count;
}
System.out.println(total+len);
}
}

• I tried hard to find a way to make it faster, but I couldn't. I give up. Do you have reasons to believe that it can be made faster? – Mike Nakis Dec 29 '11 at 22:01
• @MikeNakis One more approach of solving it is by making an arrays of suffixes and compare each with the main one and writing the similarity to output.Donno it might reduce some time. As u know here, what i did here is getting the string and comparing suffixes on the run. The puzzle where it's shown, shows me this Time Limit Exceeded 7/10 testcases passed So, it ran out of time while executing testcases. And time limit of puzzle execution time for java is 5secs. – cypronmaya Dec 29 '11 at 22:11

Converting the input String to char[] helps a little bit but I cannot profile it now.

private void solve2(final String input) {
int total = 0;
final char[] inputArray = input.toCharArray();
for (int i = 1; i < inputArray.length; i++) {
int count = 0;
for (int j = i; j < inputArray.length; j++) {
if (inputArray[j - i] != inputArray[j]) {
break;
}
count++;
}
total = total + count;
}
System.out.println(total + inputArray.length);
}


String.charAt does some index checks, so I suppose the cause of the performance improvement is the missing checks.

public char charAt(int index) {
if ((index < 0) || (index >= count)) {
throw new StringIndexOutOfBoundsException(index);
}
return value[index + offset];
}


Anyway, profile the code. Modern IDEs usually have profiler.

Another idea is using multiple threads.

• I am pretty sure that what you need is an algorithmic optimization, and not a little hack, which is bound to yield an improvement that gets factored out (doesn't register) in terms of big-oh notation. – Mike Nakis Dec 30 '11 at 7:04

I think you need a suffix tree.

Its a data structure that puts all the prefixes of a string in a tree. This makes a number of operations faster, and I think you can make your similarity metric qualify.

• Doch! I thought of this, and then I thought that the time you'd spend building this tree would be larger than the time you'd spend to just answer the question the straightforward way, but now that I am thinking about it again, I realize this: your 'solve' function can save the prefix tree of each string it sees, so as to reuse it later if it gets invoked with the same string! And I'll bet you that they make the test last 5 seconds largely by feeding it the same string over and over again, instead of producing a new string every time. – Mike Nakis Dec 30 '11 at 7:01

Efficiency

Your solve() is O(n2), where n is the length of the input string.

As it turns out, there is an O(n) algorithm to produce exactly the lengths of the common prefixes you want, called the Z Algorithm. In the standard terminology used to describe the algorithm, each of those common prefixes is called a "Z-box". A full explanation of the algorithm is beyond the scope of this review, but you should be able to find some online resources that illustrate it well. The basic idea is that information about previously analyzed Z-boxes can be used for shortcuts.

Here is a Python implementation, which translates very easily into Java.

Driver

I suggest writing main() this way:

public static void main(String[] args) {
try (Scanner scanner = new Scanner(System.in)) {
int numCases = scanner.nextInt();
while (numCases-- > 0) {
System.out.println(sum(z(scanner.next())));
}
}
}


Note the following improvements:

• Open the Scanner using a try-with-resources block.
• Use static methods. new Solution() is pointless, since the object keeps no state.
• Rename the no_cases variable according to javaConventions.
• Eliminate the i variable.
• Separate concerns, such that finding the prefix lengths, summing, and printing are done in separate functions.