1

次のコードを書いて、 とa のJavaの交点を見つけました。prefixsuffixStringJava

// you can also use imports, for example:
// import java.math.*;
import java.util.*;
class Solution {
    public int max_prefix_suffix(String S) {
        if (S.length() == 0) {
            return 1;
        }
        // prefix candidates
        Vector<String> prefix = new Vector<String>();
        // suffix candidates
        Vector<String> suffix = new Vector<String>();
        // will tell me the difference
        Set<String> set = new HashSet<String>();

        int size = S.length();
        for (int i = 0; i < size; i++) {
            String candidate = getPrefix(S, i);
            // System.out.println( candidate );
            prefix.add(candidate);
        }

        for (int i = size; i >= 0; i--) {
            String candidate = getSuffix(S, i);
            // System.out.println( candidate );
            suffix.add(candidate);
        }

        int p = prefix.size();
        int s = suffix.size();
        for (int i = 0; i < p; i++) {
            set.add(prefix.get(i));
        }
        for (int i = 0; i < s; i++) {
            set.add(suffix.get(i));
        }

        System.out.println("set: " + set.size());
        System.out.println("P: " + p + " S: " + s);
        int max = (p + s) - set.size();
        return max;
    }

    // codility
    // y t i l i d o c
    public String getSuffix(String S, int index) {
        String suffix = "";
        int size = S.length();
        for (int i = size - 1; i >= index; i--) {
            suffix += S.charAt(i);
        }

        return suffix;
    }

    public String getPrefix(String S, int index) {
        String prefix = "";
        for (int i = 0; i <= index; i++) {
            prefix += S.charAt(i);
        }

        return prefix;
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        String t1 = "";
        String t2 = "abbabba";
        String t3 = "codility";

        System.out.println(sol.max_prefix_suffix(t1));
        System.out.println(sol.max_prefix_suffix(t2));
        System.out.println(sol.max_prefix_suffix(t3));

        System.exit(0);
    }
}

いくつかのテストケースは次のとおりです。

String t1 = "";
String t2 = "abbabba";
String t3 = "codility";

期待値は次のとおりです。

1, 4, 0

私のアイデアは、候補を生成してベクトルにプッシュし、次に候補をprefix見つけてaにプッシュし、最後に両方を aにプッシュしてから差を計算することでした。しかし、私は得ています。誰かが私が間違っていることを理解するのを手伝ってもらえますか?suffixvectorvectorsSet1, 7, and 0

4

4 に答える 4

2

私はあなたの方法を次のように書きます：

public int max_prefix_suffix(String s) {
    final int len = s.length();
    if (len == 0) {
        return 1; // there's some dispute about this in the comments to your post
    }
    int count = 0;
    for (int i = 1; i <= len; ++i) {
        final String prefix = s.substring(0, i);
        final String suffix = s.substring(len - i, len);
        if (prefix.equals(suffix)) {
            ++count;
        }
    }
    return count;
}

プレフィックスをサフィックスの逆と比較する必要がある場合は、次のようにします。

final String suffix = new StringBuilder(s.substring(len - i, len))
    .reverse().toString();
于 2012-11-04T17:34:54.670 に答える
0

@ted Hop によるコードが優れていることがわかります。この質問は、特定の文字列のサフィックスとプレフィックスで一致する文字の最大数を返すように指定されています。これは適切なサブセットです。したがって、文字列全体はこの最大数では考慮されません。

元。"abbabba"、接頭辞と接尾辞には abba(最初の 4 文字) - abba (最後の 4 文字) を含めることができるため、長さ 4 codility,, prefix(c, co,cod,codi,co...),, sufix ( y、ty、ity、lity....)、どれも同じではありません。したがって、ここの長さは 0 です。

ここからカウントを変更することにより

if (prefix.equals(suffix)) {
    ++count;
}

と

if (prefix.equals(suffix)) {
    count = prefix.length();// or suffix.length()
}

最大長を取得します。しかし、これはO（n）で行うことができますか..文字列の組み込み関数は、O（n）を取ると信じているため、全体的な複雑さはO（n2）になります.....

于 2013-04-28T11:44:38.827 に答える
0

@ ravi.zombie O(n) の長さが必要な場合は、Ted のコードを次のように変更するだけです。

int max =0;
for (int i = 1; i <= len-1; ++i) {
    final String prefix = s.substring(0, i);
    final String suffix = s.substring(len - i, len);
    if (prefix.equals(suffix) && max < i) {
        max =i;
}
    return max;
}

また、適切なプレフィックスとサフィックスを取得するために文字列比較全体を省略したため、入力文字列 abbabba に対して 7 ではなく 4 が返されるはずです。

于 2013-09-27T23:02:25.467 に答える