In [1]:

    

func z(s string) []int {
    // Use Z-algorithm to preprocess given string.  See
    // Gusfield for complete description of algorithm.
    Z := make([]int, len(s)+1)
    Z[0] = len(s)
    
    // Initial comparison of s[1:] with prefix
    for i := 1; i < len(s); i++ {
        if s[i] == s[i-1] {
            Z[1] += 1
        } else {
            break
        }
    }
    
    r, l := 0, 0
    if Z[1] > 0 {
        r, l = Z[1], 1
    }
    
    for k := 2; k < len(s); k++ {
        if k > r {
            // Case 1
            for i := k; i < len(s); i++ {
                if s[i] == s[i-k] {
                    Z[k] += 1
                } else {
                    break
                }
            }
            r, l = k + Z[k] - 1, k
        } else {
            // Case 2
            // Calculate length of beta
            nbeta := r - k + 1
            Zkp := Z[k - l]
            if nbeta > Zkp {
                // Case 2a: Zkp wins
                Z[k] = Zkp
            } else {
                // Case 2b: Compare characters just past r
                nmatch := 0
                for i := r+1; i < len(s); i++ {
                    if s[i] == s[i - k] {
                        nmatch += 1
                    } else {
                        break
                    }
                }
                l, r = k, r + nmatch
                Z[k] = r - k + 1
            }
        }
    }
    return Z
}


    

In [2]:

    

z("abracadabra")
// abracadabra (11)
//    a        (1)
//      a      (1)
//        abra (4)
//           a (1)


    

    
Out[2]:





[11 0 0 1 0 1 0 4 0 0 1 0]

In [3]:

    

z("aaaaa")


    

    
Out[3]:





[5 4 3 2 1 0]

In [4]:

    

func zMatch(p, t string) []int {
    s := p + "$" + t
    Z := z(s)
    occurrences := []int{}
    for i := len(p) + 1; i < len(s); i++ {
        if Z[i] >= len(p) {
            occurrences = append(occurrences, i - (len(p) + 1))
        }
    }
    return occurrences
}


    

In [5]:

    

zMatch("needle", "haystack needle haystack")
//                012345678901234567890123
//                          1         2


    

    
Out[5]:





[9]

In [6]:

    

zMatch("needle", "haystack needle needle")
//                0123456789012345678901
//                          1         2


    

    
Out[6]:





[9 16]