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

これが質問です-

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 です。

コードの実行速度を改善するにはどうすればよいですか。Web サイトは使用するテスト ケースのリストを提供しないため、さらに難しくなります。

4

5 に答える 5

3

別のアルゴリズムを使用しました。ループを n 回実行します。ここで、n はメイン ストリングの長さに等しくなります。for each ループは、i 番目の文字列から始まる文字列のすべてのサフィックスを生成し、2 番目の文字列と一致させます。一致しない文字が見つかったら、ループを中断し、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 に答える
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 に答える
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 に答える
0

サンプル文字列の長さで初期化simし、外側のループを 1 で開始します。これは、サンプル文字列とそれ自体を比較すると、独自の長さの値が結果に追加されることが事前にわかっているためです。

于 2012-07-13T23:07:43.140 に答える