java后缀Trie匹配,匹配操作出现问题
我面临后缀Trie匹配的问题,我设计了一个后缀Trie,带有一个26路树来表示节点中的字符加上与每个节点相关的值。每个节点的值表示字符串(如果是后缀)在主字符串中开始的索引或-1。此后,我试图让匹配操作工作,但显然它没有,我无法在这里找到错误。有关更多说明,请参阅Second Question in this Pdf。请帮忙
import java.util.*;
class node{
public int val;
public node ptrs[];
node(){
this.val =0;
ptrs = new node[26];
for (node ptr : ptrs) {
ptr = null;
}
}
}
class Tree{
public node root = new node();
int pass =0;
void insert(String s,int indx) {
node trv = root;
for (int i = 0; i < s.length(); i++) {
if (trv.ptrs[s.charAt(i) - 'A'] == null) {
trv.ptrs[s.charAt(i) - 'A'] = new node();
if(i==s.length()-1){
trv.ptrs[s.charAt(i)-'A'].val = indx;
}else{
trv.ptrs[s.charAt(i)-'A'].val = -1;
}
}
trv = trv.ptrs[s.charAt(i) - 'A'];
}
}
private void visit(node trv){
for(int i =0;i<26;i++){
if(trv.ptrs[i]!=null){
System.out.println(trv.ptrs[i].val+":"+((char)(i+'A')));
visit(trv.ptrs[i]);
}
}
}
void visit(){
this.visit(root);
}
void leaf(node trv){
if(trv.val>=0){
System.out.println(trv.val);
}else{
for(int i=0;i<26;i++){
if(trv.ptrs[i]!=null){
if(trv.ptrs[i].val>=0){
System.out.println(trv.ptrs[i].val);
}else{
leaf(trv.ptrs[i]);
}
}
}
}
}
private void search(node trv,String s,int i){
if(i<=s.length()-1){
if(trv.ptrs[s.charAt(i)-'A']!=null){
if(i==s.length()-1){
leaf(trv.ptrs[s.charAt(i)-'A']);
}else{
search(trv.ptrs[s.charAt(i)-'A'], s, i+1);
}
}
}
}
void query(String s){
this.search(root, s, 0);
}
}
public class Trie {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
Tree t = new Tree();
String txt = sc.next();
int txtLen = txt.length();
for(int i =0;i<txtLen;i++){
t.insert(txt.substring(i,txtLen),i);
}
int q = sc.nextInt();
while(q-->0){
String m = sc.next();
t.query(m);
}
sc.close();
}
}
预期:
Input:
AATCGGGTTCAATCGGGGT
2
ATCG
GGGT
Output:
1 4 11 15
我的输出:
AATCGGGTTCAATCGGGGT
2
ATCG
11
1
GGGT
4
我没有得到你所看到的15分的答案
# 1 楼答案
我试图调查你的程序,但你的程序写得不好,不幸的是我找不到你的问题。我试图通过
visit
打印它,但没有有用的信息但是下面尝试通过后缀树查找模式,后缀树在Fast Pattern Matching of Strings Using Suffix Tree中描述。也许有帮助: