範圍搜索3列的字符串

Question

我已經設置字符串像下面 A.B.C

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。

Answer 1

此代碼可能會對您有所幫助。

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]); 
} 

Answer 2

如果你的字符串集基本上是固定的（不經常更新），那麼簡單的排序列表就可以。要查找帶有前綴的所有字符串，請在該列表上執行二進制搜索，找到第一個字符串。然後在字符串匹配前綴的同時迭代。

就內建的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字符得到一個字符串大於任何匹配前綴的最佳方式。做這部分可​​能有更好的方法。

Answer 3

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] 

Answer 4

我的功能：

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

Answer 5

您可以創建一個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. ^是爲了權力。