17

文字列が与えられ、連続した部分文字列として 2 回s含まれる最短の文字列を返す必要があるメソッドを作成する必要があります。s

ただし、 の 2 つのオカレンスはs重複する場合があります。例えば、

  • aba戻り値ababa
  • xxxxx戻り値xxxxxx
  • abracadabra戻り値abracadabracadabra

これまでの私のコードは次のとおりです。

import java.util.Scanner;

public class TwiceString {

    public static String getShortest(String s) {
        int index = -1, i, j = s.length() - 1;
        char[] arr = s.toCharArray();
        String res = s;

        for (i = 0; i < j; i++, j--) {
            if (arr[i] == arr[j]) {
                index = i;
            } else {
                break;
            }
        }

        if (index != -1) {
            for (i = index + 1; i <= j; i++) {
                String tmp = new String(arr, i, i);
                res = res + tmp;
            }
        } else {
            res = res + res;
        }

        return res;
    }

    public static void main(String args[]) {
        Scanner inp = new Scanner(System.in);
        System.out.println("Enter the string: ");
        String word = inp.next();

        System.out.println("The requires shortest string is " + getShortest(word));
    }
}

コーディング レベルではなく、アルゴリズム レベルでおそらく間違っていることはわかっています。私のアルゴリズムは何ですか？

4

6 に答える 6

9

サフィックス ツリーを使用します。特に、 のツリーを構築した後、s文字列全体を表すリーフに移動し、別の文字列の終わりマーカーが表示されるまで上に移動します。これは、接頭辞でもある最長の接尾辞の葉になりますs。

于 2012-07-15T08:42:09.247 に答える
3

@phs が既に述べたように、問題の一部は「s の接尾辞でもある s の最長の接頭辞を見つける」ように変換でき、ツリーのない解決策は次のようになります。

public static String getShortest(String s) {
    int i = s.length();
    while(i > 0 && !s.endsWith(s.substring(0, --i))) 
        ;
    return s + s.substring(i);
}
于 2012-07-15T12:07:12.867 に答える
2

Knuth-Morris-Prattアルゴリズムを確認する必要があると思います。使用する部分一致テーブルは、必要なものとほぼ同じです (ちなみに、これは非常に優れたアルゴリズムです ;)

于 2012-07-15T12:37:43.717 に答える
2

インデックスが見つかったら、それが -1 の場合でも、元の文字列にindex + 1(インデックスは最後に一致する文字インデックスであるため) 文字列の末尾までの部分文字列を追加するだけです。String には、この部分文字列を取得するメソッドがあります。

于 2012-07-15T07:48:38.650 に答える
0

たとえば、入力文字列sが である場合"abcde"、次のような正規表現を簡単に作成できます (最後の文字"e"が欠落していることに注意してください!)。

a(b(c(d)?)?)?$

string で実行しますs。これは、末尾の繰り返される部分文字列の開始位置を返します。次に、欠落している部分 (つまり、 の最後の NM 文字s、N は の長さs、M は一致の長さ) を追加するだけです。たとえば、

aba
  ^ match "a"; append the missing "ba"
xxxxxx
 ^ match "xxxxx"; append the missing "x"
abracadabra
       ^ match "abra"; append the missing "cadabra"
nooverlap
--> no match; append "nooverlap"
于 2012-07-15T09:02:37.273 に答える
-1

私の理解から、あなたはこれをしたい：

input: dog
output: dogdog
--------------
input: racecar
output: racecaracecar

だから、これは私がそれを行う方法です：

 public String change(String input)
{
    StringBuilder outputBuilder = new StringBuilder(input);

    int patternLocation = input.length();
    for(int x = 1;x < input.length();x++)
    {
        StringBuilder check = new StringBuilder(input);

        for(int y = 0; y < x;y++)
            check.deleteCharAt(check.length() - 1);

        if(input.endsWith(check.toString()))
        {
            patternLocation = x;
            break;
        }
    }

    outputBuilder.delete(0,  input.length() - patternLocation);

    return outputBuilder.toString();
}

これが役に立ったことを願っています！

于 2012-07-15T07:54:22.663 に答える