7

我正在尝试解决 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
ababaa
aa

样本输出：
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。

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

4

5 回答 5

3

我使用 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;
}
于 2012-07-17T23:52:30.470 回答
3

使用了不同的算法。运行 n 次循环，其中 n 等于主字符串的长度。对于每个循环，生成从第 i 个字符串开始的字符串的所有后缀，并将其与第二个字符串匹配。当你发现不匹配的字符打破循环时，将 j 的值添加到计数器整数 c。

import java.io.BufferedReader;
import java.io.InputStreamReader;

class Solution {

    public static void main(String args[]) throws Exception {
    BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
    int T = Integer.parseInt(in.readLine());
    for (int i = 0; i < T; i++) {
        String line = in.readLine();
        System.out.println(count(line));
    }
    }

    private static int count(String input) {
    int c = 0, j;
    char[] array = input.toCharArray();
    int n = array.length;
    for (int i = 0; i < n; i++) {
        for (j = 0; j < n - i && i + j < n; j++)
        if (array[i + j] != array[j])
            break;
        c+=j;
    }
    return c;
    }
}
于 2012-11-03T12:09:33.377 回答
1

我花了一些时间来解决这个问题，这是我的代码示例（它适用于我，并通过所有测试用例）：

static long stringSimilarity(String a) {
        int len=a.length();
        char[] letters = a.toCharArray();
        char localChar = letters[0];
        long sim=0;
        int sameCharsRow = 0;
        boolean isFirstTime = true;
        for(int i=0;i<len;i++){
            if (localChar == letters[i]) {
                for(int j = i + sameCharsRow;j<len;j++){
                    if (isFirstTime && letters[j] == localChar) {
                        sameCharsRow++;
                    } else {
                        isFirstTime = false;
                    }
                    if(letters[j-i]==letters[j])
                        sim++;
                    else
                        break;
                }
                if (sameCharsRow > 0) {
                    sameCharsRow--;
                    sim += sameCharsRow;
                }
                isFirstTime = true;
            }
        }
        return sim;
}

关键是我们需要对相同内容的字符串进行加速，然后我们在测试用例 10 和 11 下会有更好的性能。

于 2017-04-21T13:11:15.920 回答
0

使用样本字符串的长度进行初始化sim，并以 1 开始外循环，因为我们现在提前将样本字符串与其自身的比较将其自己的长度值添加到结果中。

于 2012-07-13T23:07:43.140 回答
0 
import java.util.Scanner;

public class StringSimilarity 
{
public static void main(String args[])
 {
  Scanner user_input = new Scanner(System.in);
  int count = Integer.parseInt(user_input.next());
  char[] nextLine = user_input.next().toCharArray();
    try 
     {
       while(nextLine!= null )
       {
  int length = nextLine.length;
  int suffixCount =length;
  for(int i=1;i<length;i++)
  {
          int j =0;
          int k=i;
          for(;k<length && nextLine[k++] == nextLine[j++];  suffixCount++);
  }
       System.out.println(suffixCount);
      if(--count < 0)
      {
      System.exit(0);
      }
    nextLine = user_input.next().toCharArray();
     }
   }
   catch (Exception e) 
   {
   // TODO Auto-generated catch block
   e.printStackTrace();
   }
  }
}
于 2012-07-15T20:12:49.163 回答