go语言几种算法（三）
13、Rabin-Karp(Rabin-Karp字符串匹配算法)
package main
import (
"fmt"
)
const base = 16777619
func Search(txt string, patterns []string) []string {
in := indices(txt, patterns)
matches := make([]string, len(in))
i := 0
for j, p := range patterns {
if _, ok := in[j]; ok {
matches[i] = p
i++
}
}
return matches
}
func indices(txt string, patterns []string) map[int]int {
n, m := len(txt), minLen(patterns)
matches := make(map[int]int)
if n < m || len(patterns) == 0 {
return matches
}
var mult uint32 = 1 // mult = base^(m-1)
for i := 0; i < m-1; i++ {
mult = (mult * base)
}
hp := hashPatterns(patterns, m)
h := hash(txt[:m])
for i := 0; i < n-m+1 && len(hp) > 0; i++ {
if i > 0 {
h = h - mult*uint32(txt[i-1])
h = h*base + uint32(txt[i+m-1])
}
if mps, ok := hp[h]; ok {
for _, pi := range mps {
pat := patterns[pi]
e := i + len(pat)
if _, ok := matches[pi]; !ok && e <= n && pat == txt[i:e] {
matches[pi] = i
}
}
}
}
return matches
}
func hash(s string) uint32 {
var h uint32
for i := 0; i < len(s); i++ {
h = (h*base + uint32(s[i]))
}
return h
}
func hashPatterns(patterns []string, l int) map[uint32][]int {
m := make(map[uint32][]int)
for i, t := range patterns {
h := hash(t[:l])
if _, ok := m[h]; ok {
m[h] = append(m[h], i)
} else {
m[h] = []int{i}
}
}
return m
}
func minLen(patterns []string) int {
if len(patterns) == 0 {
return 0
}
m := len(patterns[0])
for i := range patterns {
if m > len(patterns[i]) {
m = len(patterns[i])
}
}
return m
}
func main() {
txt := "Australia is a country and continent surrounded by the Indian and Pacific oceans."
patterns := []string{"and", "the", "surround", "Pacific", "Germany"}
matches := Search(txt, patterns)
fmt.Println(matches)
}
14、LIFO Stack and FIFO Queue(栈，队列)
package main
import (
"fmt"
)
type Node struct {
Value int
}
func (n *Node) String() string {
return fmt.Sprint(n.Value)
}
// NewStack returns a new stack.
func NewStack() *Stack {
return &Stack{}
}
// Stack is a basic LIFO stack that resizes as needed.
type Stack struct {
nodes []*Node
count int
}
// Push adds a node to the stack.
func (s *Stack) Push(n *Node) {
s.nodes = append(s.nodes[:s.count], n)
s.count++
}
// Pop removes and returns a node from the stack in last to first order.
func (s *Stack) Pop() *Node {
if s.count == 0 {
return nil
}
s.count--
return s.nodes[s.count]
}
// NewQueue returns a new queue with the given initial size.
func NewQueue(size int) *Queue {
return &Queue{
nodes: make([]*Node, size),
size: size,
}
}
// Queue is a basic FIFO queue based on a circular list that resizes as needed.
type Queue struct {
nodes []*Node
size int
head int
tail int
count int
}
// Push adds a node to the queue.
func (q *Queue) Push(n *Node) {
if q.head == q.tail && q.count > 0 {
nodes := make([]*Node, len(q.nodes)+q.size)
copy(nodes, q.nodes[q.head:])
copy(nodes[len(q.nodes)-q.head:], q.nodes[:q.head])
q.head = 0
q.tail = len(q.nodes)
q.nodes = nodes
}
q.nodes[q.tail] = n
q.tail = (q.tail + 1) % len(q.nodes)
q.count++
}
// Pop removes and returns a node from the queue in first to last order.
func (q *Queue) Pop() *Node {
if q.count == 0 {
return nil
}
node := q.nodes[q.head]
q.head = (q.head + 1) % len(q.nodes)
q.count--
return node
}
func main() {
s := NewStack()
s.Push(&Node{3})
s.Push(&Node{5})
s.Push(&Node{7})
s.Push(&Node{9})
fmt.Println(s.Pop(), s.Pop(), s.Pop(), s.Pop())
q := NewQueue(1)
q.Push(&Node{2})
q.Push(&Node{4})
q.Push(&Node{6})
q.Push(&Node{8})
fmt.Println(q.Pop(), q.Pop(), q.Pop(), q.Pop())
}
15、Median of Medians(中位数的中位数)
package main
import "fmt"
type Node struct {
prev *Node
next *Node
key interface{}
}
type List struct {
head *Node
tail *Node
}
func (L *List) Insert(key interface{}) {
list := &Node{
next: L.head,
key: key,
}
if L.head != nil {
L.head.prev = list
}
L.head = list
l := L.head
for l.next != nil {
l = l.next
}
L.tail = l
}
func (l *List) Display() {
list := l.head
for list != nil {
fmt.Printf("%+v ->", list.key)
list = list.next
}
fmt.Println()
}
func Display(list *Node) {
for list != nil {
fmt.Printf("%v ->", list.key)
list = list.next
}
fmt.Println()
}
func ShowBackwards(list *Node) {
for list != nil {
fmt.Printf("%v <-", list.key)
list = list.prev
}
fmt.Println()
}
func (l *List) Reverse() {
curr := l.head
var prev *Node
l.tail = l.head
for curr != nil {
next := curr.next
curr.next = prev
prev = curr
curr = next
}
l.head = prev
Display(l.head)
}
func main() {
link := List{}
link.Insert(5)
link.Insert(9)
link.Insert(13)
link.Insert(22)
link.Insert(28)
link.Insert(36)
fmt.Println("\n==============================\n")
fmt.Printf("Head: %v\n", link.head.key)
fmt.Printf("Tail: %v\n", link.tail.key)
link.Display()
fmt.Println("\n==============================\n")
fmt.Printf("head: %v\n", link.head.key)
fmt.Printf("tail: %v\n", link.tail.key)
link.Reverse()
fmt.Println("\n==============================\n")
}
16、Longest Common Sub-sequence(最长公共子序列)
package main
import "fmt"
type Node struct {
prev *Node
next *Node
key interface{}
}
type List struct {
head *Node
tail *Node
}
func (L *List) Insert(key interface{}) {
list := &Node{
next: L.head,
key: key,
}
if L.head != nil {
L.head.prev = list
}
L.head = list
l := L.head
for l.next != nil {
l = l.next
}
L.tail = l
}
func (l *List) Display() {
list := l.head
for list != nil {
fmt.Printf("%+v ->", list.key)
list = list.next
}
fmt.Println()
}
func Display(list *Node) {
for list != nil {
fmt.Printf("%v ->", list.key)
list = list.next
}
fmt.Println()
}
func ShowBackwards(list *Node) {
for list != nil {
fmt.Printf("%v <-", list.key)
list = list.prev
}
fmt.Println()
}
func (l *List) Reverse() {
curr := l.head
var prev *Node
l.tail = l.head
for curr != nil {
next := curr.next
curr.next = prev
prev = curr
curr = next
}
l.head = prev
Display(l.head)
}
func main() {
link := List{}
link.Insert(5)
link.Insert(9)
link.Insert(13)
link.Insert(22)
link.Insert(28)
link.Insert(36)
fmt.Println("\n==============================\n")
fmt.Printf("Head: %v\n", link.head.key)
fmt.Printf("Tail: %v\n", link.tail.key)
link.Display()
fmt.Println("\n==============================\n")
fmt.Printf("head: %v\n", link.head.key)
fmt.Printf("tail: %v\n", link.tail.key)
link.Reverse()
fmt.Println("\n==============================\n")
}
17、Levenshtein distance(编辑距离-字符串相似度算法)
package main
import "fmt"
func levenshtein(str1, str2 []rune) int {
s1len := len(str1)
s2len := len(str2)
column := make([]int, len(str1)+1)
for y := 1; y <= s1len; y++ {
column[y] = y
}
for x := 1; x <= s2len; x++ {
column[0] = x
lastkey := x - 1
for y := 1; y <= s1len; y++ {
oldkey := column[y]
var incr int
if str1[y-1] != str2[x-1] {
incr = 1
}
column[y] = minimum(column[y]+1, column[y-1]+1, lastkey+incr)
lastkey = oldkey
}
}
return column[s1len]
}
func minimum(a, b, c int) int {
if a < b {
if a < c {
return a
}
} else {
if b < c {
return b
}
}
return c
}
func main(){
var str1 = []rune("Asheville")
var str2 = []rune("Arizona")
fmt.Println("Distance between Asheville and Arizona:",levenshtein(str1,str2))
str1 = []rune("Python")
str2 = []rune("Peithen")
fmt.Println("Distance between Python and Peithen:",levenshtein(str1,str2))
str1 = []rune("Orange")
str2 = []rune("Apple")
fmt.Println("Distance between Orange and Apple:",levenshtein(str1,str2))
}
18、Knuth–Morris–Pratt(KMP-克努斯-莫里斯-普拉特算法-子串匹配算法)
package main
import (
"fmt"
)
const (
PatternSize int = 100
)
func SearchNext(haystack string, needle string) int {
retSlice := KMP(haystack, needle)
if len(retSlice) > 0 {
return retSlice[len(retSlice)-1]
}
return -1
}
func SearchString(haystack string, needle string) int {
retSlice := KMP(haystack, needle)
if len(retSlice) > 0 {
return retSlice[0]
}
return -1
}
func KMP(haystack string, needle string) []int {
next := preKMP(needle)
i := 0
j := 0
m := len(needle)
n := len(haystack)
x := []byte(needle)
y := []byte(haystack)
var ret []int
//got zero target or want, just return empty result
if m == 0 || n == 0 {
return ret
}
//want string bigger than target string
if n < m {
return ret
}
for j < n {
for i > -1 && x[i] != y[j] {
i = next[i]
}
i++
j++
//fmt.Println(i, j)
if i >= m {
ret = append(ret, j-i)
//fmt.Println("find:", j, i)
i = next[i]
}
}
return ret
}
func preMP(x string) [PatternSize]int {
var i, j int
length := len(x) - 1
var mpNext [PatternSize]int
i = 0
j = -1
mpNext[0] = -1
for i < length {
for j > -1 && x[i] != x[j] {
j = mpNext[j]
}
i++
j++
mpNext[i] = j
}
return mpNext
}
func preKMP(x string) [PatternSize]int {
var i, j int
length := len(x) - 1
var kmpNext [PatternSize]int
i = 0
j = -1
kmpNext[0] = -1
for i < length {
for j > -1 && x[i] != x[j] {
j = kmpNext[j]
}
i++
j++
if x[i] == x[j] {
kmpNext[i] = kmpNext[j]
} else {
kmpNext[i] = j
}
}
return kmpNext
}
func main() {
fmt.Println("Search First Position String:\n")
fmt.Println(SearchString("cocacola", "co"))
fmt.Println(SearchString("Australia", "lia"))
fmt.Println(SearchString("cocacola", "cx"))
fmt.Println(SearchString("AABAACAADAABAABA", "AABA"))
fmt.Println("\nSearch Last Position String:\n")
fmt.Println(SearchNext("cocacola", "co"))
fmt.Println(SearchNext("Australia", "lia"))
fmt.Println(SearchNext("cocacola", "cx"))
fmt.Println(SearchNext("AABAACAADAABAABAAABAACAADAABAABA", "AABA"))
}
发表评论：