最长重复字符串题解 golang

最长重复字符串题解

package main

import (
    "fmt"
    "strings"
)

type Index map[int]int

type Counter map[string]Index

var c = make(Counter)

func setRecord(match string, index int) {
    i, ok := c[match]
    if !ok {
        i = make(Index)
        c[match] = i
        return
    }

    i[index]++
}

func filterOverlap() {
    var keys []string
    for k := range c {
        keys = append(keys, k)
    }

    for _, xkey := range keys {
        for k := range c {
            if strings.HasPrefix(xkey, k) && xkey != k {
                // fmt.Printf("delete key=%v\n", k)
                delete(c, k)
                continue
            }
        }
    }
}

func calc(sample []byte) {
    var i, n, xi, xj, yi, yj int
    n = len(sample)

    var a, b string

    for i = 0; i < n; i++ {
        for xi = i; xi < n-1; xi++ {
            for xj = xi + 1; xj < n; xj++ {
                for yi = xj + 1; yi < n; yi++ {

                    yj = yi + (xj - xi)
                    a = string(sample[xi:xj])
                    b = string(sample[yi:yj])
                    if a == b {
                        setRecord(a, xi)
                        setRecord(b, yi)
                    }

                }
            }
        }
    }
}

func main() {
    var s = "12342342341234"

    calc([]byte(s))

    filterOverlap()

    for k, v := range c {
        fmt.Printf("%v:%v\n", k, len(v))
    }
}

有疑问加站长微信联系（非本文作者）