Java实现双数组Trie树(DoubleArrayTrie,DAT) - JAVA

t index)
{
ArrayList result = new ArrayList();
if(Base[index] == 0)
{
result.add("");
return result;
}
if(Base[index] < 0)
{
String r="";
for(int i=-Base[index];Tail[i]!=END_CHAR;++i)
{
r+= Tail[i];
}
result.add(r);
return result;
}
for(int i=1;i<=CharMap.size();++i)
{
if(Check[Base[index]+i] == index)
{
for(String s:GetAllChildWord(Base[index]+i))
{
result.add(CharList.get(i)+s);
}
//result.addAll(GetAllChildWord(Base[index]+i));
}
}
return result;
}

public ArrayList FindAllWords(String word)
{
ArrayList result = new ArrayList();
String prefix = "";
FindStruct fs = Find(word);
int p = fs.p;
if (p == -1) return result;
if(Base[p]<0)
{
String r="";
for(int i=-Base[p];Tail[i]!=END_CHAR;++i)
{
r+= Tail[i];
}
result.add(fs.prefix+r);
return result;
}

if(Base[p] > 0)
{
ArrayList r = GetAllChildWord(p);
for(int i=0;i {
r.set(i, fs.prefix+r.get(i));
}
return r;
}

return result;
}

}
/*
* Name: Double Array Trie
* Author: Yaguang Ding
* Date: 2012/5/21
* Note: a word ends may be either of these two case:
* 1. Base[cur_p] == pos ( pos<0 and Tail[-pos] == 'END_CHAR' )
* 2. Check[Base[cur_p] + Code('END_CHAR')] == cur_p
*/

import java.util.ArrayList;
import java.util.HashMap;
import java.util.Map;
import java.util.Arrays;

public class DoubleArrayTrie {
final char END_CHAR = '\0';
final int DEFAULT_LEN = 1024;
int Base[] = new int [DEFAULT_LEN];

int Check[] = new int [DEFAULT_LEN];
char Tail[] = new char [DEFAULT_LEN];
int Pos = 1;
Map CharMap = new HashMap();
ArrayList CharList = new ArrayList();

public DoubleArrayTrie()
{
Base[1] = 1;

CharMap.put(END_CHAR,1);
CharList.add(END_CHAR);
CharList.add(END_CHAR);
for(int i=0;i<26;++i)
{
CharMap.put((char)('a'+i),CharMap.size()+1);
CharList.add((char)('a'+i));
}

}
private void Extend_Array()
{
Base = Arrays.copyOf(Base, Base.length*2);
Check = Arrays.copyOf(Check, Check.length*2);
}

private void Extend_Tail()
{
Tail = Arrays.copyOf(Tail, Tail.length*2);
}

private int GetCharCode(char c)
{
if (!CharMap.containsKey(c))
{
CharMap.put(c,CharMap.size()+1);
CharList.add(c);
}
return CharMap.get(c);
}
private int CopyToTailArray(String s,int p)
{
int _Pos = Pos;
while(s.length()-p+1 > Tail.length-Pos)
{
Extend_Tail();
}
for(int i=p; i {
Tail[_Pos] = s.charAt(i);
_Pos++;
}
return _Pos;
}

private int x_check(Integer []set)
{
for(int i=1; ; ++i)
{
boolean flag = true;
for(int j=0;j {
int cur_p = i+set[j];
if(cur_p>= Base.length) Extend_Array();
if(Base[cur_p]!= 0 || Check[cur_p]!= 0)
{
flag = false;
break;
}
}
if (flag) return i;
}
}

private ArrayList GetChildList(int p)
{
ArrayList ret = new ArrayList();
for(int i=1; i<=CharMap.size();++i)
{
if(Base[p]+i >= C

Java实现双数组Trie树(DoubleArrayTrie,DAT) (五)