3

go 实现indexOf，leetCode28

 3 years ago
source link: https://studygolang.com/articles/35577
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
neoserver,ios ssh client

go indexOf

indexOf

indexOf(s, p string) 函数会返回p在s中首次出现的位置，倘如没有则返回-1，本次使用之前提到过的kmp算法来作为indexOf的核心，并用来解决leetcode28题

func strStr(haystack string, needle string) int {

    return indexOf(haystack, needle)
}

func indexOf(s, p string) int {
    if len(p) == 0 {
        return 0
    }
    next := make([]int, len(p))
    next[0] = -1

    j := -1
    for i := 1; i < len(p); i++ {
        for j != -1 && p[i] != p[j+1] {
            j = next[j]
        }
        if p[i] == p[j+1] {
            j++
        }
        next[i] = j
    }

    j = -1
    for i := 0; i < len(s); i++ {
        for j != -1 && s[i] != p[j+1] {
            j = next[j]
        }
        if s[i] == p[j+1] {
            j++
        }

        if j == len(p) - 1 {
            return i - j
        }
    }
    return -1
}

report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK