Go中如何找到最长匹配子串

Question

找到最长子串匹配的正确方法是什么？ 我一直在尝试在 Go 中找到与 regexp 包匹配的最长子字符串： https://pkg.go。 dev/regexp

特别是字符串中元音的最长连续匹配。 “aeiou”的任意长度或组合。

这是我现在的代码。它会一直工作，直到字符串变得太长而导致恐慌（超过 1000）。我开始搜索最长的子字符串，并在找到匹配项后返回。

s := "chrononhotonthuooaos"
for i := utf8.RuneCountInString(s); i >=0; i-- {
    exp := "[aeiou]{"
    exp += fmt.Sprint(i)
    exp += "}"
    regexStr := regexp.MustCompile(exp)
    longestStr := regexStr.FindStringSubmatch(s)
    if longestStr != nil {
        fmt.Println("longest submatch found:", longestStr)
        return utf8.RuneCountInString(longestStr[0])
    }
}
return 0

Answer 1

您感到恐慌的原因是因为您在每次迭代中创建一个新的正则表达式 - 一个 10,000 个字符的字符串？这是 10,000 个已编译的正则表达式，我很确定它们会被缓存。更不用说正则表达式编译的成本很高。

那么为什么要使用正则表达式呢？像这样的东西几乎肯定更快，不会创建任何中间对象，并且以 O(n) 时间和 O(1) 空间复杂度运行。它适用于任何长度的字符串：

https://goplay.tools/snippet/nvZwWeEF8bC

func longest_vowel_run(s string) (string, int, int) {
    slen := len(s)
    bgn := 0
    end := 0
    max := 0
    x := 0
    y := 0

    // while we still have chars left...
    for x < len(s) {

        // find the first vowel
        for x < slen && !vowel[s[x]] {
            x++
        }
        // find the next non-vowel
        for y = x; y < slen && vowel[s[y]]; {
            y++
        }

        // if the current run is longer than the max run, update the max run
        if z := y - x; z > max {
            bgn = x
            end = y
            max = z
        }

        // pick up where we left off
        x = y

    }

    var maxRun string
    if max > 0 {
        maxRun = s[bgn:end]
    }

    return maxRun, bgn, end - 1
}

var vowel = map[byte]bool{
    'a': true, 'A': true,
    'e': true, 'E': true,
    'i': true, 'I': true,
    'o': true, 'O': true,
    'u': true, 'U': true,
}

Answer 2

您可以执行以下操作：

re := regexp.MustCompile(`[aeiou]+`)

matches := re.FindAllStringSubmatch(s, -1)
if len(matches) > 0 {
    longest := 0
    for i := range matches {
        if len(matches[i]) >= len(matches[longest]) {
            longest = i
        }
    }
    fmt.Println(matches[longest])
}

https://go.dev/play/p/loxIsR3LMOM

---

或者，如果没有正则表达式，您可以执行以下操作：

s := "chrononhotonthuooaos"

var start, end int
for i := 0; i < len(s); i++ {
    switch s[i] {
    case 'a', 'e', 'i', 'o', 'u':
        j := i + 1
        for ; j < len(s); j++ {
            switch s[j] {
            case 'a', 'e', 'i', 'o', 'u':
                continue
            }
            break
        }
        if j-i > end-start {
            start, end = i, j
        }
        i = j
    }
}

fmt.Println(s[start:end])

https://go.dev/play/p/XT5-pr3n0tl

Answer 3

这是我的答案。虽然它不像同伴那样优雅，但对我来说很有效。 https://go.dev/play/p/ZpZtqt92lvc

package main

import (
"fmt"
"regexp"
)

func main() {

word := "chrononhotonthuooaos"
//word := "aeoihddkdhuaiahdnaanbcvuuooaaiieendjahaaaiiie"

// only vowels allowed (one or more)
re := regexp.MustCompile(`[aeiou]+`)

// to store max length slice of vowel macthes
max_length := 0

// position of the max lenghth slice inside `vowels_matches`
position := 0

// type ~~~~> [][]byte{}  all coincident slices inside another
vowels_matches := re.FindAll([]byte(word), -1)

for i := 0; i < len(vowels_matches); i++ {

    // Looking for the longest slice with vowels
    // so we are going to compare its lengths

    if len(vowels_matches[i]) > max_length {

        //if we find an slice longer max_length will take its value
        max_length = len(vowels_matches[i])

        // also we want to know the position, to pick after that slice in concret
        position = i
    }
}

// get that slice of bytes (the longest) an convert to string
result := string(vowels_matches[position])

fmt.Printf("%v type ~~~> %T\n", result, result)

}

另一种不使用正则表达式的选项借助小递归函数：https://go.dev/play/p/7sssSWv-0UL

package main

import (
  "fmt"
)

func main() {

    word := "chrononhotonthuooaos"

    pattern := "aeiou"

    // we only want all vowels inside `word` variable
    // so `vowels` will append the positions inside `word`
    vowels := []int{}

    // slice of slices of vowel matches
    vowels_matches := [][]int{}

    // to store max length of vowel macthes slices
    max_length := 0

    // position of the max lenghth slice inside `vowels_matches`
    position := 0

    final_string_result := ""

    // append only vowels from `word`
    for i, vowel := range word {
        for _, v := range pattern {
            if v == vowel {
                vowels = append(vowels, i) //append the position of that vowel

            }
        }
    }

    vowels_matches = recursive(int(vowels[0]), vowels, vowels_matches)

    for i := 0; i < len(vowels_matches); i++ {
        if len(vowels_matches[i]) > max_length {
            max_length = len(vowels_matches[i])
            position = i
        }
    }

    for _, e := range vowels_matches[position] {
        final_string_result += string(word[e])
    }

    fmt.Println(final_string_result)

}

func recursive(valid int, vowels []int, vowels_matches [][]int) [][]int {

    temp := []int{}

    for i, value := range vowels {
        if value == valid+1 || i == 0 {
            valid = value
            temp = append(temp, value)
        } else {
            next_last := int(vowels[i:][0])
            new_slice := vowels[i:]
            vowels_matches = recursive(next_last, new_slice, vowels_matches)
        }
    }

    vowels_matches = append(vowels_matches, temp)

    return vowels_matches
}