找到最長子字串匹配的正確方法是什么？我一直在嘗試找到與 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
uj5u.com熱心網友回復：
您感到恐慌的原因是因為您在每次迭代時都創建了一個新的正則運算式——一個 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,
}
uj5u.com熱心網友回復：
您可以執行以下操作：
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
uj5u.com熱心網友回復：
這是我的答案。雖然它不像同伴那樣優雅，但它對我有用。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
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qiye/433692.html
上一篇：為什么替換所有方法不起作用？