Concept of Rabin Karp Algorithm

README.md

Drawback: Spurious Hits

rabin-karp-algorithm-concept.go

package main

import "fmt"

type pattern struct {
	hashValue int
	length    int
}

var mapping = make(map[string]int)

func assignStringMap() {
	for ch := 'A'; ch <= 'z'; ch++ {
		mapping[string(ch)] = int(ch) - 64
	}
}

func hashStringToInt(fullString string) pattern {
	val := 0

	for _, ch := range fullString {
		val += mapping[string(ch)]
	}

	return pattern{
		hashValue: val,
		length:    len(fullString),
	}
}

func rabinKarpAlgo(fullString string, pattern pattern) bool {
	length := pattern.length
	hashValue := pattern.hashValue
	val := 0
	fullStringLength := len(fullString)
	if length > fullStringLength {
		return false
	}

	for i := range length {
		ch := fullString[i]
		val += mapping[string(ch)]
	}

	if val == hashValue {
		return true
	}

	for i := length; i < fullStringLength; i++ {
		firstChar := fullString[i-length]
		currChar := fullString[i]

		val = val + mapping[string(currChar)] - mapping[string(firstChar)]

		if val == hashValue {
			return true
		}
	}

	return false
}

func main() {
	assignStringMap()
	pattern := "aaa"
	fullString := "aaabc"
	matchingStatus := rabinKarpAlgo(fullString, hashStringToInt(pattern))
	if matchingStatus {
		fmt.Println("String **matched** using Rabin Karp algorithm")
	} else {
		fmt.Println("String **not matched** using Rabin Karp algorithm")
	}
}