JAVA AC自动机算法，后缀自动机
你能理解KMP算法么？如果可以，KMP其实就是AC自动机只有一个模式串的情况。或者说，AC自动机是KMP的树形扩展。
■网友
ArbrePrefixes(Iterable\u0026lt;String\u0026gt; s) throws FileNotFoundException{
racine=new Noeud(\u0026#39;.\u0026#39;,null,false);//racine = 根
Iterator\u0026lt;String\u0026gt; iter = s.iterator();
while(iter.hasNext()){
Scanner buffer = new Scanner(iter.next());//new file
buffer.useDelimiter("");
Character symboleLu;
Noeud pere = this.racine;
boolean prefixe=false;
while (buffer.hasNext()) {
symboleLu = buffer.next().charAt(0);
if(!buffer.hasNext()){prefixe=true;}
CreerFilsManquant(pere,symboleLu,prefixe);
pere=pere.listeFils.get(symboleLu);}//pere=父节点
buffer.close();
}}
//找后缀
public void trouverSuffixe(){
if(this==racine){
noeudCandidat=racine;
【JAVA AC自动机算法，后缀自动机】 }
else{
noeudCandidat = this.pere.suffixe;
}
while(true){
if (noeudCandidat.listeFils.get(this.caractere)!=null \u0026amp;\u0026amp; noeudCandidat.listeFils.get(this.caractere)!=this){
suffixe=noeudCandidat.listeFils.get(this.caractere);
}
if(suffixe!=null){break;}
else{
if(noeudCandidat.pere == null){
suffixe=racine;
}
else{
noeudCandidat=noeudCandidat.pere;
}
}
}
}
//找符合的后缀
public void trouverSuffixeAcceptant(){
if(suffixe.prefixeMotDico){
suffixeAcceptant=suffixe;
}
else{
suffixeAcceptant=suffixe.suffixeAcceptant;
}
if(suffixeAcceptant==null){
suffixeAcceptant=racine;
}}
public void VerifierOccurence(){
try {
URL url = AhoCorasick.class.getClassLoader().getResource("");
Iterator\u0026lt;String\u0026gt; it = ConstruitDictionnaire(url.getFile()+"CyranoDeBergerac.txt").iterator();
Noeud noeudEnCours=racine;
Noeud noeudSuffixe;
int compteur = 0;
while(it.hasNext()){
String mot = it.next();
Scanner buffer = new Scanner(mot);//new file
buffer.useDelimiter("");
Character symboleLu;
//char ch = mot.toCharArray();
while (buffer.hasNext()) {
compteur ++;
symboleLu =buffer.next().charAt(0);
Character tiret=new Character(\u0026#39;-\u0026#39;);
if((Character.isLetter(symboleLu))||(symboleLu.equals(tiret)))
{
if(noeudEnCours!=null \u0026amp;\u0026amp; noeudEnCours.listeFils.get(symboleLu)!=null){
noeudEnCours=noeudEnCours.listeFils.get(symboleLu);
if (noeudEnCours.prefixeMotDico){
Occurence occ = new Occurence(mot,compteur);
System.out.println("--nouedSuffixe=racine-------"+compteur);
}
noeudSuffixe=noeudEnCours.suffixeAcceptant;
while(noeudSuffixe !=racine){
Occurence occ = new Occurence(mot, compteur);
System.out.println("---noeudSuffixe------"+compteur);
noeudEnCours=noeudSuffixe;
noeudSuffixe=noeudSuffixe.suffixeAcceptant;
}
}
else{
noeudEnCours=racine.listeFils.get(symboleLu);
推荐阅读
- dart这编程语言现在发展怎么样了，语法与Java，c#很相似，甚至更简洁
- Java工程师和C++工程师在工作上有啥区别哪个更适合自身发展
- 为啥这个算法误差的看起来这么小
- 27岁，转行java的血与泪，该何去何从
- |伊朗核科学家系遭远程自动机枪射击身亡 暗杀行动三分钟
- 怎样统计工程中未使用的java类
- 新互联网网站用Java还靠谱么对比Php，Python，Ruby的话
- 我想学java和安卓软件开发?
- 使用算法帮助人们筛选reader的信息是否存在可能
- 学计算机专业，java那些和网站开发选台式还是笔记本好