Calculating sum of similarities of strings

Question

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);
    }
}

Answer 1

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.

Answer 2

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.

Answer 3

Efficiency

Your solve() is O(n²), 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.