模式查找问题

给定文本txt[0…N-1] 和 模式pat[0…M-1]，假设是n > m。
写一个函数search(char pat[]， char txt[])，打印txt[]中所有出现的pat[]

如查找一段核苷酸序列的片段在基因组中的位置

实现思路

基于后缀字典树实现字符串的模式查找
查找的时间复杂度为O(m+k)，其中m为模式的长度，k为模式在文本中出现的次数

如何构建树

• 生成给定字符串的所有后缀。
• 把所有的后缀作为一个字符串，构建Trie

示例如下图，如构建字符串banana的后缀字典树，方式如下：

如何查找

• 从模式字符串的第一个字符和Trie 的树根开始，针对每个字符 做如下操作：
  • 对于当前字符，如果从当前节点有一条边，则沿着这条边继续。
  • 如果没有边，打印“pattern doesn’t exist in text”并返回。
• 如果模式的所有字符都被处理过，即给定模式的字符，存在一条来自根的路径，则打印模式存在的所有索引。

实现源码示例

import java.util.LinkedList;
import java.util.List;
class SuffixTreeTest{
    public static void main(String args[]) {
        String txt = "this is a beautiful world";
        SuffixTree tree = new SuffixTree(txt);

        //打印模式出现的位置
        System.out.println("Search for 'beauti'");
        tree.searchTree("beati");

        System.out.println("Search for 'is'");
        tree.searchTree("is");
    }
}

class SuffixTree{
    SuffixTrieNode root = new SuffixTrieNode();

    SuffixTree(String txt) {
        for (int i = 0; i < txt.length(); i++) {
            root.insertSuffix(txt.substring(i), i);
        }
    }
    void searchTree(String pat) {
        if(pat.length()>0) {
            List<Integer> result = root.search(pat);
            if (result == null) {
                System.out.println("Pattern not found");
            } else {
                int patLen = pat.length();
                for (Integer i : result) {
                    System.out.println("Pattern found at position " + (i - patLen));
                }
            }
        }
        System.out.println("length of Pattern must > 0 ");
    }

    private class SuffixTrieNode {
        final static int MAX_CHAR = 256;

        SuffixTrieNode[] children = new SuffixTrieNode[MAX_CHAR];
        List<Integer> indexes;

        SuffixTrieNode() {
            indexes = new LinkedList<Integer>();
            for (int i = 0; i < MAX_CHAR; i++) {
                children[i] = null;
            }
        }

        void insertSuffix(String s, int index) {
            indexes.add(index);
            if (s.length() > 0) {
                char cIndex = s.charAt(0);
                if (children[cIndex] == null) {
                    children[cIndex] = new SuffixTrieNode();
                }
                children[cIndex].insertSuffix(s.substring(1), index + 1);
            }
        }

        List<Integer> search(String s) {
            if (s.length() == 0) {
                return indexes;
            }

            if (children[s.charAt(0)] != null) {
                return (children[s.charAt(0)]).search(s.substring(1));
            } else {
                return null;
            }
        }
    }
}