[20.8] strsStr, find mutliple substring within a string

1. Example

Suffix Trie or LeetCode: Implement strStr

http://www.geeksforgeeks.org/pattern-searching-set-8-suffix-tree-introduction/

LeetCode: Implement strStr one-to-one()
public int strStr(String haystack, String needle) {
1.brute-force   :Time O(n*m),    SpaceO(1)
2.Rolling Hash:Time O(n)     ,    Space:O(1), concern: Big integer ('z'-'a')*26^8 
3.KMP             :Time O(n)     ,    Space:O(1)
where n is the length of haystack

CC150: Suffix tree  strsStr one-to-many()
public int[] strsStr(String haystack, String[] needles) {

1. suffix tree    : Time O(m), Space:O(n)where m is the length of needles

http://www.geeksforgeeks.org/pattern-searching-set-8-suffix-tree-introduction/

Let us consider an example text “banana\0″ where ‘\0′ is string termination character. Following are all suffixes of “banana\0″

banana\0
anana\0
nana\0
ana\0
na\0
a\0
\0

Build a standard Trie
f we consider all of the above suffixes as individual words and build a trie, we get following


Derive a Compressed Trie
If we join chains of single nodes, we get the following compressed trie, which is the Suffix Tree for given text “banana\0″


       0 1 2 3
A1: b i  b s

s
ibs
b s
    ibs
                         root
            /              |         \
           B   0,2     I   1      S 3
         /    \           |      
       I0      S2     B  1
       |                   |
       B0               S 1
       |
       S0

1. SuffixTree: all you need to do is search for each string in T in the suffix tree.

Note that if “B” were a word, you would come up with two locations

String testString = "mississippi";
String[] stringList = {"is", "sip", "hi", "sis"};

Implement strStr multiple times ( String needle, String hayStack )
multiple needles need to check if a substring of hayStack
2. KMP multiple times => KMP:O(m) * n
n smaller strings => n prefix table

2. Implementation

Q1: suffix tree for s (hayStack)
A1: bibs
 
s
ibs
b s
    ibs
Q1:
   

  public class Question {
  public static void main(String[] args) {
  String testString = “mississippi”;
  String[] stringList = {“is”, “sip”, “hi”, “sis”};
  SuffixTree tree = new SuffixTree(testString);
  for (String s : stringList) {
  ArrayList list = tree.getIndexes(s);
  if (list != null) {
  System.out.println(s + “: “ + list.toString());
  }
  }
  }
  }


// Create the tree with the root
 
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 getIndexes(String s) {
  return root.getIndexes(s);
  }
  }
 
  public class SuffixTreeNode {
  HashMap children = new
  HashMap();
  char value;
  ArrayList indexes = new ArrayList();
  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 getIndexes(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).getIndexes(remainder);
  }
  }
  return null;
  }
  }
 

3. Similar Ones