题目

给定一个较长字符串big和一个包含较短字符串的数组smalls，设计一个方法，根据smalls中的每一个较短字符串，对big进行搜索。

输出smalls中的字符串在big里出现的所有位置positions，其中positions[i]为smalls[i]出现的所有位置。

示例：输入：big = "mississippi" smalls = ["is","ppi","hi","sis","i","ssippi"]

输出： [[1,4],[8],[],[3],[1,4,7,10],[5]]

提示：0 <= len(big) <= 1000

0 <= len(smalls[i]) <= 1000

smalls的总字符数不会超过 100000。

你可以认为smalls中没有重复字符串。

所有出现的字符均为英文小写字母。

解题思路分析

1、内置函数；时间复杂度O(n^2log(n))，空间复杂度O(n^2)

func multiSearch(big string, smalls []string) [][]int {
   n := len(smalls)
   res := make([][]int, n)
   arr := suffixarray.New([]byte(big)) // 创建后缀树
   for i := 0; i < n; i++ {
      target := []byte(smalls[i])
      temp := arr.Lookup(target, -1) // 返回arr中所有target出现的位置，从后往前
      sort.Ints(temp)
      res[i] = temp
   }
   return res
}

2、暴力法；时间复杂度O(n^3)，空间复杂度O(n^2)

func multiSearch(big string, smalls []string) [][]int {
   n := len(smalls)
   res := make([][]int, n)
   for i := 0; i < n; i++ {
      arr := make([]int, 0)
      if smalls[i] == "" {
         res[i] = arr
         continue
      }
      for j := 0; j+len(smalls[i]) <= len(big); j++ {
         if big[j:j+len(smalls[i])] == smalls[i] {
            arr = append(arr, j)
         }
      }
      res[i] = arr
   }
   return res
}

3、字典树；时间复杂度O(n^2)，空间复杂度O(n^2)

func multiSearch(big string, smalls []string) [][]int {
   n := len(smalls)
   res := make([][]int, n)
   root := &Trie{
      next: [26]*Trie{},
   }
   for i := 0; i < n; i++ {
      root.Insert(smalls[i], i+1)
   }
   for i := 0; i < len(big); i++ {
      temp := root.Search(big[i:])
      for j := 0; j < len(temp); j++ {
         res[temp[j]] = append(res[temp[j]], i)
      }
   }
   return res
}

type Trie struct {
   next   [26]*Trie // 下一级指针，如不限于小写字母，[26]=>[256]
   ending int       // 下标，从1开始
}

// 插入word
func (this *Trie) Insert(word string, index int) {
   temp := this
   for _, v := range word {
      value := v - 'a'
      if temp.next[value] == nil {
         temp.next[value] = &Trie{
            next:   [26]*Trie{},
            ending: 0,
         }
      }
      temp = temp.next[value]
   }
   temp.ending = index
}

// 查找
func (this *Trie) Search(word string) []int {
   arr := make([]int, 0) // 存放匹配到的下标列表
   temp := this
   for _, v := range word {
      value := v - 'a'
      if temp = temp.next[value]; temp == nil {
         return arr
      }
      if temp.ending > 0 {
         arr = append(arr, temp.ending-1)
      }
   }
   return arr
}

总结

Medium题目，使用暴力法或者借助字典树