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

您可以创建一个 3d 树（kd-tree 的一种特殊情况）。然后对类似的东西进行搜索a1.b1.*，你对a1.b1.c1_minand进行范围搜索a1.b1.c1_max。并对输出进行排序。

这将为您O (n ^ (2/3) + r)提供搜索和O (r log (r))排序，其中n是所有节点r的数量并且是找到的节点的数量。

搜索复杂度来自一般 kd-tree 的搜索复杂度：O(n ^ (1-1/k) + r)在 3d 树的情况下，k是 3.^的幂。

于 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.*");

使用nextPrefix有点难看，因为我假设前缀始终是 -.分隔部分的序列，并且附加 FFFF 字符是获得大于任何匹配前缀的字符串的最佳方法。这部分可能有更好的方法。

于 2013-03-21T04:46:11.817 回答
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

我的功能：

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 回答