java - interviewstreet.com - 字符串相似度

Question

我正在尝试解决 interviewstreet.com 上的字符串相似性问题。我的代码适用于 7/10 个案例(并且超过了其他 3 个案例的时间限制)。

这是我的代码 -

public class Solution {

    public static void main(String[] args) {

        Scanner user_input = new Scanner(System.in);

        String v1 = user_input.next();
        int number_cases = Integer.parseInt(v1);

        String[] cases = new String[number_cases];
        for(int i=0;i<number_cases;i++)
            cases[i] = user_input.next();

        for(int k=0;k<number_cases;k++){
            int similarity = solve(cases[k]);   
            System.out.println(similarity);
        }
    }

    static int solve(String sample){

        int len=sample.length();
        int sim=0;
        for(int i=0;i<len;i++){
            for(int j=i;j<len;j++){
                if(sample.charAt(j-i)==sample.charAt(j))
                    sim++;
                else
                    break;
            }
        }
        return sim;
    }
}

这是问题-

对于两个字符串 A 和 B，我们将字符串的相似度定义为两个字符串共有的最长前缀的长度。例如字符串“abc”和“abd”的相似度为2，而字符串“aaa”和“aaab”的相似度为3。

计算字符串 S 及其每个后缀的相似度之和。

输入:
第一行包含测试用例的数量T。接下来的T行每行包含一个字符串。

输出:
输出包含相应测试用例答案的 T 行。

约束:
1 <= T <= 10
每个字符串的长度最多为100000，并且只包含小写字符。

示例输入:
2
阿巴巴
一个

示例输出:
11
3

解释:
对于第一种情况，字符串的后缀是“ababaa”、“babaa”、“abaa”、“baa”、“aa”和“a”。这些字符串中的每一个与字符串“ababaa”的相似度分别为 6,0,3,0,1,1。因此答案是 6 + 0 + 3 + 0 + 1 + 1 = 11。

对于第二种情况，答案是 2 + 1 = 3。

如何提高代码的运行速度。由于该网站未提供其使用的测试用例列表，因此变得更加困难。

Answer 1

我使用 char[] 而不是字符串。它将运行时间从 5.3 秒减少到 4.7 秒，并且对于测试用例，它起作用了。这是代码 -

static int solve(String sample){    
        int len=sample.length();
        char[] letters = sample.toCharArray();
        int sim=0;
        for(int i=0;i<len;i++){
            for(int j=i;j<len;j++){
                if(letters[j-i]==letters[j])
                    sim++;
                else
                    break;
            }
        }
    return sim;
}