0

私は1つのコードをプログラムしましたが、1つのテストケースに合格しただけなので、私が行ったすべての間違いと、コードに加えなければならないすべての変更を理解していないため、質問とコードは次のとおりです。

質問：

2 つの文字列 A と B について、文字列の類似性を、両方の文字列に共通する最長のプレフィックスの長さと定義します。たとえば、文字列「abc」と「abd」の類似度は 2 ですが、文字列「aaa」と「aaaab」の類似度は 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 番目のケースの場合、答えは 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 に答える