3

以下のabcのような文字列のセットがあります

a1.b1.c1
a1.b1.c2
a1.b2.c3
a2.b1.c1
a2.b2.c2
a3.b3.c3

要求された場合a1.*、 から始まるすべての文字列を返す必要がありますa1。を求められた場合a1.b1、から始まるすべての文字列を返す必要がありますa1.b1

すべての出力はソートされている必要があります（辞書式）

データ構造に関する提案は、私が考えていたSuffix Tree.

4

5 に答える 5

0

NavigabeeSet は、そのようなことをすばやく行うことができます。

    NavigableSet<String> s = new TreeSet<>();
    s.addAll(Arrays.asList("a1.b1.c1", "a1.b1.c2", "a1.b2.c3", "a2.b1.c1"));
    System.out.println(s.subSet("a1.", true, "a2", false)); // a1.*
    System.out.println(s.tailSet("a1.b1"));                 // a1.b1

出力

[a1.b1.c1, a1.b1.c2, a1.b2.c3]
[a1.b1.c1, a1.b1.c2, a1.b2.c3, a2.b1.c1]
于 2013-03-21T05:04:06.560 に答える
0

このコードはあなたを助けるかもしれません。

String stringarray[] = {"a1.b1.c1",
"a1.b1.c2",
"a1.b2.c3",
"a2.b1.c1",
"a2.b2.c2",
"a3.b3.c3"};
String startingfrom = "a1.b1";
for(int i = 0; i < stringarray.length;i++) {
     if(stringarray[i].startsWith(startingfrom))
              System.out.println("string is : " + stringarray[i]);
}
于 2013-03-21T04:42:53.637 に答える
0

3d ツリーを作成できます (kd-tree の特殊なケース)。次に、 のような検索をa1.b1.*行うには、 と で範囲検索をa1.b1.c1_min行いa1.b1.c1_maxます。そして、出力をソートします。

これによりO (n ^ (2/3) + r)、検索とO (r log (r))並べ替えが可能になります。ここnで、 はすべてのノードrの数であり、 は見つかったノードの数です。

検索複雑度は、一般的な kd ツリーの検索複雑度に従いO(n ^ (1-1/k) + r)ます。k^

于 2013-03-21T08:02:54.480 に答える
0

文字列のセットが基本的に固定されている (頻繁に更新されない) 場合は、単純なソート済みリストで問題ありません。プレフィックスを持つすべての文字列を見つけるには、そのリストでバイナリ検索を実行し、最初の文字列を見つけます。次に、文字列がプレフィックスに一致する間、その時点から繰り返します。

組み込みの Java データ構造に関しては、TreeSet を使用することをお勧めします。

SortedSet<String> data = new TreeSet<String>();

Set<String> findMatching(SortedSet<String> data, String prefix) {
    String prefix = prefix.replace("*", ""); // remove unnecessary *
    String nextPrefix = prefix + '\uffff'; // a string guaranteed to be after anything matching the prefix
    // get the subset after the prefix, and then get the subset of that before the prefix
    return data.tailSet(prefix).headSet(nextPrefix, false);
}

findMatching(data, "a1.b1.*");

プレフィックスは常に - で区切られた部分のシーケンスであり、プレフィックスに一致する文字列よりも大きな文字列を取得するには FFFF 文字を追加するのが最善の方法であると想定しているため、使用nextPrefixは少し醜いです。.この部分を行うためのより良い方法があるかもしれません。

于 2013-03-21T04:46:11.817 に答える
0

私の機能:

class Match
{
    public static ArrayList<String> match (String[] data, String regex)
    {
        ArrayList<String> m = new ArrayList<String>();

        for (String d : data)
        {
            if (d.matches(regex))
            {
                m.add(d);
            }
        }

        Collections.sort(m);

        return m;
    }
}

テスト：

String data [] =
{"a1.b1.c1",
 "a1.b1.c2",
 "a1.b2.c3",
 "a2.b1.c1",
 "a2.b2.c2",
 "a3.b3.c3"};

// match using a regular expression
ArrayList<String> matched = match (data, "^a1\.b1.*");
于 2013-03-21T06:27:53.957 に答える