Go实现KMP和Sunday算法

本文主要是介绍Go实现KMP和Sunday算法，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

KMP

 1 func KMP(str, substr string) int {
 2    if substr == "" {
 3       return 0
 4    }
 5    strLen := len(str)
 6    subLen := len(substr)
 7    next := make([]int, subLen)
 8    for i, j := 1, 0; i < subLen; i++ {
 9       for j > 0 && substr[i] != substr[j] {
10          j = next[j-1]
11       }
12       if substr[i] == substr[j] {
13          j++
14       }
15       next[i] = j
16    }
17    for i, j := 0, 0; i < strLen; i++ {
18       for j > 0 && str[i] != substr[j] {
19          j = next[j-1]
20       }
21       if str[i] == substr[j] {
22          j++
23       }
24       if j == subLen {
25          return i - subLen + 1
26       }
27    }
28    return -1
29 }

Sunday

func Sunday(str, substr string) int {
   if len(substr) == 0 {
      return 0
   }
   strLen := len(str)
   subLen := len(substr)
   if subLen > strLen {
      return -1
   }
   m := make(map[rune]int, 0)
   for index, c := range substr {
      m[c] = index
   }
   start, compareCount := 0, 0
   for start+subLen <= strLen {
      compareCount = 0
      for str[start+compareCount] == substr[compareCount] {
         compareCount++
         if compareCount == subLen {
            return start
         }
      }
      checkIndex := start + subLen
      var lastIndex int
      if checkIndex < strLen {
         lastIndex = m[rune(str[checkIndex])]
      } else {
         lastIndex = -1
      }
      if lastIndex != -1 {
         start += subLen - lastIndex
      } else {
         start += start + subLen + 1
      }
   }
   return -1
}

这篇关于Go实现KMP和Sunday算法的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！