首页 > 代码库 > 18.8 suffix tree
18.8 suffix tree
给定一个字符串s 和 一个包含较短字符串的数组t，设计一个方法，根据t中的每一个较短的字符换，对s进行搜索。
思路：基于s建立后缀树，然后在后缀树中进行查找，返回所有可能的索引值。
import java.util.ArrayList;public class Question { public static void main(String[] args) { String testString = "bibs"; String[] stringList = {"b", "bs", "hi", "bb"}; SuffixTree tree = new SuffixTree(testString); for (String s : stringList) { ArrayList<Integer> list = tree.search(s); if (list != null) { System.out.println(s + ": " + list.toString()); } } }}
/**
b: [0, 2]
bs: [2]
*/
import java.util.ArrayList;public class SuffixTree { SuffixTreeNode root = new SuffixTreeNode(); public SuffixTree(String s) { for (int i = 0; i < s.length(); i++) { String suffix = s.substring(i); root.insertString(suffix, i); } } public ArrayList<Integer> search(String s) { return root.search(s); }}
package Question18_8;import java.util.ArrayList;import java.util.HashMap;public class SuffixTreeNode { HashMap<Character, SuffixTreeNode> children = new HashMap<Character, SuffixTreeNode>(); char value; ArrayList<Integer> indexes = new ArrayList<Integer>(); public SuffixTreeNode() { } public void insertString(String s, int index) { indexes.add(index); if (s != null && s.length() > 0) { value = s.charAt(0); SuffixTreeNode child = null; if (children.containsKey(value)) { child = children.get(value); } else { child = new SuffixTreeNode(); children.put(value, child); } String remainder = s.substring(1); child.insertString(remainder, index); } } public ArrayList<Integer> search(String s) { if (s == null || s.length() == 0) { return indexes; } else { char first = s.charAt(0); if (children.containsKey(first)) { String remainder = s.substring(1); return children.get(first).search(remainder); } } return null; }}
18.8 suffix tree
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。