96 lines
1.7 KiB
Go
96 lines
1.7 KiB
Go
|
package main
|
||
|
|
|
||
|
|
import "fmt"
|
||
|
|
|
||
|
|
func main() {
|
||
|
|
|
||
|
|
fmt.Println(findAnagrams("cbaebabacd", "abc"))
|
||
|
|
|
||
|
|
}
|
||
|
|
|
||
|
|
func findAnagrams(s string, p string) []int {
|
||
|
|
length := len(p)
|
||
|
|
if length > len(s) {
|
||
|
|
return []int{}
|
||
|
|
}
|
||
|
|
nums := [26]int{}
|
||
|
|
nownum := [26]int{}
|
||
|
|
result := []int{}
|
||
|
|
|
||
|
|
for _, ch := range p {
|
||
|
|
nums[ch-'a']++
|
||
|
|
}
|
||
|
|
|
||
|
|
for i := 0; i < len(s)-length+1; i++ {
|
||
|
|
if i == 0 {
|
||
|
|
for i := 0; i < length; i++ {
|
||
|
|
nownum[s[i]-'a']++
|
||
|
|
}
|
||
|
|
if nums == nownum {
|
||
|
|
result = append(result, i)
|
||
|
|
}
|
||
|
|
continue
|
||
|
|
}
|
||
|
|
|
||
|
|
nownum[s[i-1]-'a']--
|
||
|
|
nownum[s[i+length-1]-'a']++
|
||
|
|
|
||
|
|
if nums == nownum {
|
||
|
|
result = append(result, i)
|
||
|
|
}
|
||
|
|
}
|
||
|
|
|
||
|
|
return result
|
||
|
|
}
|
||
|
|
|
||
|
|
//func findAnagrams(s string, p string) []int {
|
||
|
|
// result := make([]int, 0)
|
||
|
|
// if len(s) < len(p) {
|
||
|
|
// return result
|
||
|
|
// }
|
||
|
|
// windowlength := len(p)
|
||
|
|
// hashmap := make(map[string]int)
|
||
|
|
// keynum := 0
|
||
|
|
// for i := range p {
|
||
|
|
// if _, ok := hashmap[string(p[i])]; ok {
|
||
|
|
// hashmap[string(p[i])] += 1
|
||
|
|
// } else {
|
||
|
|
// keynum++
|
||
|
|
// hashmap[string(p[i])] = 1
|
||
|
|
// }
|
||
|
|
// }
|
||
|
|
// //fmt.Println(hashmap)
|
||
|
|
// for slow := 0; slow < len(s); slow++ {
|
||
|
|
// fasttmp := slow
|
||
|
|
// hashtemp := make(map[string]int)
|
||
|
|
// if len(s)-fasttmp < windowlength {
|
||
|
|
// break
|
||
|
|
// }
|
||
|
|
// for fast := slow; fast < windowlength+slow; fast++ {
|
||
|
|
// if _, ok := hashmap[string(s[fast])]; ok {
|
||
|
|
// hashtemp[string(s[fast])] += 1
|
||
|
|
// } else {
|
||
|
|
// break
|
||
|
|
// }
|
||
|
|
// if fast == windowlength+slow-1 {
|
||
|
|
// va := 0
|
||
|
|
// for k, v := range hashtemp {
|
||
|
|
// if hashmap[k] != v {
|
||
|
|
// //fmt.Println("退出")
|
||
|
|
// break
|
||
|
|
// } else {
|
||
|
|
// va++
|
||
|
|
// }
|
||
|
|
// }
|
||
|
|
// //fmt.Println("当前va:", va)
|
||
|
|
// if va == keynum {
|
||
|
|
// result = append(result, slow)
|
||
|
|
// }
|
||
|
|
// }
|
||
|
|
// }
|
||
|
|
// //fmt.Println("hashtemp", hashtemp)
|
||
|
|
// }
|
||
|
|
// fmt.Println(result)
|
||
|
|
// return result
|
||
|
|
//}
|