求给定子串的next[]数组

    1. // nextArr 确定一个子串的next数组
    2. func nextArr(str string) []int {
    3.     var slice = make([]int, 0)
    4.     slice = append(slice, -1)
    5.     for i := 2; i <= len(str); i++ {
    6.         var j = 1
    7.         for {
    8.             prefix := str[:i-1-j]
    9.             suffix := str[j : i-1]
    10.             if prefix != "" && prefix == suffix {
    11.                 slice = append(slice, len(prefix))
    12.                 break
    13.             }
    14.             j++
    15.             if j >= i {
    16.                 slice = append(slice, 0)
    17.                 break
    18.             }
    19.         }
    20.     }
    21.     return slice
    22. }

    根据next数组及查找目标字符串位置

    1. func FindStr(origin string, target string) int {
    2.     if target == origin {
    3.         return 0
    4.     }
    5.     if origin == "" {
    6.         return -1
    7.     }
    8.     // next数组
    9.     arr := nextArr(target)
    10.     return findStr(origin, target, arr)
    11. }
    13. // findStr 私有查找字符串
    14. func findStr(str string, target string, arr []int) int {
    15.     var i = 0
    16.     var j = 0
    17.     for {
    18.         origin := str[i]
    19.         t := target[j]
    20.         if origin == t {
    21.             i++
    22.             j++
    23.         } else {
    24.             next := arr[j]
    25.             if next < 0 {
    26.                 // 移动源字符串
    27.                 i++
    28.             } else {
    29.                 // 移动模式串
    30.                 j = next
    31.             }
    32.         }
    33.         if j == len(target) || i == len(str) {
    34.             break
    35.         }
    36.     }
    38.     if j == len(target) {
    39.         return i - len(target)
    40.     } else {
    41.         return -1
    42.     }
    43. }

    demo

    1. func main() {
    2.     var str = "abcababcdsdohjd"
    3.     var target = "ababcd"
    4.     arr := nextArr(target)
    5.     fmt.Println("next数组：", arr)
    6.     //
    7.     index := FindStr(str, target)
    8.     if index < 0 {
    9.         fmt.Println("未找到目标字符串!")
    10.     } else {
    11.         fmt.Println("找到目标字符串，起始位置index = ", index)
    12.     }
    13. }