0

我编写了 1 个代码，但它刚刚通过了 1 个测试用例，所以我不明白我犯了哪些错误以及我要在代码中进行哪些更改，所以问题和代码如下：

问题：

对于两个字符串 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。

代码：

字符串相似度

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

public class Solution 
{
    int T,i;
    String[] S;
    String p;


    String inp;
    BufferedReader br=new BufferedReader(new InputStreamReader(System.in));

    int count=0;

    public void StringSimilarity()
    {

        try
        {
            T=Integer.parseInt(br.readLine());  
            if(T<1 && T>10)
                System.exit(0);
            S=new String[T];

        }
        catch(Exception e)
        {
        }

            for(i=0;i<T;i++)
            {
                count=0;
             try
             {

                S[i]=br.readLine();
                S[i].toLowerCase();

             }
             catch(Exception e)
            {
                System.err.println("Error:" + e.getMessage());
            }

        }


        for(i=0;i<T;i++)
        {
            int g=0;
            p=S[i];
            int a=0;
            a=p.length();
            count=0;
            char t[]=new char[a];


            for(int n=0;n<p.length();n++)
            {
                t[n]=p.charAt(n);

            }




            int m=p.length();

            for(int f=0;f<t.length;f++)
            {
                for(int j=0;j<m-g;j++)
                {
                   if(p.charAt(0)== t[0])
                   {
                    if(p.charAt(j)== t[j])
                    {
                        count=count+1;

                    }
                   }
                }
                g=g+1;


                for(int k=0;k<t.length-1;k++)
                {
                    t[k]=t[k+1];
                }
            }
            System.out.println(count);
        }
    }

    public static void main(String[] args)
    {
        Solution s=new Solution();
        s.StringSimilarity();

    }
}
4

1 回答 1

0

您的算法很难阅读，因为它包含太多变量，并且没有正确分解成更小的易于阅读、可维护和可测试的部分。我试图以一种更直接的方式来解决你的问题，这样你就可以检查它、玩弄它并从中学习一些东西。希望能帮助到你...


package test;

import java.io.BufferedReader;
import java.io.FileReader;
import java.io.IOException;
import java.io.Reader;

public class Main {

  public static void main(String[] args) {
    Main m = new Main();
    m.start();
  }

  private void start() {
    try {
      parse("x.txt");
    } catch (IOException ex) {
      ex.printStackTrace();
    }
  }

  private void parse(String filename) throws IOException {
    Reader r = null;
    try {
      r = new FileReader(filename);
      BufferedReader br = new BufferedReader(r);
      String line = null;
      while ((line = br.readLine()) != null) {
        String[] strings = line.split(" ");
        /* skip the first one, not important for us */
        for (int i = 1; i < strings.length; i++) {
          System.out.println("RESULT: for '" + strings[i] + "' is " + computeSimilarity(strings[i]));
        }
      }
    } finally {
      if (r != null) {
        r.close();
      }
    }
  }

  private int computeSimilarity(String s) {
    int result = 0;
    for (int i = 0; i < s.length(); i++) {
      /* compare also with itself */
      result += compareSimilarity(s, s.substring(i));
    }
    System.out.println("  " + s + " -> " + result);
    return result;
  }

  private int compareSimilarity(String s1, String s2) {
    int result = 0;
    /* s1.length() > s2.length() */
    for (int i = 0; i < s2.length(); i++) {
      if (s1.charAt(i) == s2.charAt(i)) {
        result++;
      } else {
        break;
      }
    }
    System.out.println("    " + s1 + " " + s2 + " -> " + result);
    return result;
  }
}

它对您的测试数据的输出是：


    ababaa ababaa -> 6
    ababaa babaa -> 0
    ababaa abaa -> 3
    ababaa baa -> 0
    ababaa aa -> 1
    ababaa a -> 1
  ababaa -> 11
RESULT: for 'ababaa' is 11
    aa aa -> 2
    aa a -> 1
  aa -> 3
RESULT: for 'aa' is 3
于 2012-04-08T21:36:41.733 回答