范围搜索3列的字符串
问题描述:
我已经设置字符串像下面 A.B.C范围搜索3列的字符串
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
。
答
此代码可能会对您有所帮助。
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]);
}
答
如果你的字符串集基本上是固定的(不经常更新),那么简单的排序列表就可以。要查找带有前缀的所有字符串,请在该列表上执行二进制搜索,找到第一个字符串。然后在字符串匹配前缀的同时迭代。
就内建的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字符得到一个字符串大于任何匹配前缀的最佳方式。做这部分可能有更好的方法。
答
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]
答
我的功能:
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.*");
答
您可以创建一个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-tree的搜索复杂度来看:O(n^(1-1/k) + r)
,在3d树的情况下,k
是3. ^
是为了权力。
一个简单的列表和一些正则表达式模式匹配来过滤元素呢? – 2013-03-21 04:38:08