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

Pos = CopyToTailArray(s,i+1);
break;
}
}
}

public boolean Exists(String word)
{
int pre_p = 1;
int cur_p = 0;

for(int i=0;i {
cur_p = Base[pre_p]+GetCharCode(word.charAt(i));
if(Check[cur_p] != pre_p) return false;
if(Base[cur_p] < 0)
{
if(TailMatchString(-Base[cur_p],word.substring(i+1)))
return true;
return false;
}
pre_p = cur_p;
}
if(Check[Base[cur_p]+GetCharCode(END_CHAR)] == cur_p)
return true;
return false;
}

//内部函数，返回匹配单词的最靠后的Base index，
class FindStruct
{
int p;
String prefix="";
}
private FindStruct Find(String word)
{
int pre_p = 1;
int cur_p = 0;
FindStruct fs = new FindStruct();
for(int i=0;i {
// BUG
fs.prefix += word.charAt(i);
cur_p = Base[pre_p]+GetCharCode(word.charAt(i));
if(Check[cur_p] != pre_p)
{
fs.p = -1;
return fs;
}
if(Base[cur_p] < 0)
{
if(TailContainString(-Base[cur_p],word.substring(i+1)))
{
fs.p = cur_p;
return fs;
}
fs.p = -1;
return fs;
}
pre_p = cur_p;
}
fs.p = cur_p;
return fs;
}

public ArrayList GetAllChildWord(int 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;
}

}

测试

[java] import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Scanner;

import javax.xml.crypto.Data;

public class Main {

public static void main(String[] args) throws Exception {
ArrayList words = new ArrayList();
BufferedReader reader = new BufferedReader(new InputStreamReader(new FileInputStream("E:/兔子的试验学习中心[课内]/ACM大赛/ACM第四届校赛/E命令提示/words3.dic")));
String s;
int num = 0;
while((s=reader.readLine()) != null)
{
words.add(s);
num ++;
}
DoubleArrayTrie dat = new DoubleArrayTrie();

for(String word: words)
{
dat.Insert(word);
}

System.out.println(dat.Base.length);
System.out.println(dat.Tail.length);

Scanner sc = new Scanner(System.in);
while(sc.hasNext())
{
String word = sc.next();
System.out.println(dat.Exists(word));
System.out.println(dat.FindAllWords(word));
}

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