RabinKarp.search_in() - Code Metrics - Inspection of "Implement rabin karp substring search" - chen0040/pyalgs - Measure and Improve Code Quality continuously with Scrutinizer

Passed

Push — master ( 999b46...f880e0 )

by Xianshun

created 2017-05-07 02:58 UTC

RabinKarp.search_in() A

↳ Parent: RabinKarp

Complexity

Conditions

Size

Total Lines

Duplication

Lines	0
Ratio	0 %

Importance

Changes	1
Bugs	0	Features	0

Metric	Value
cc	4
c	1
b	0
f	0
dl	0
loc	10
rs	9.2

from abc import ABCMeta, abstractmethod


class SubstringSearch(object):
    __metaclass__ = ABCMeta

    @abstractmethod
    def search_in(self, text):
        pass


class BruteForceSubstringSearch(SubstringSearch):
    def __init__(self, pattern):
        self.pattern = pattern

    def search_in(self, text):
        n = len(text)

        for i in range(n - len(self.pattern)):
            J = i
            for j in range(len(self.pattern)):
                k = i + j
                if text[k] != self.pattern[j]:
                    J = -1
                    break
            if J != -1:
                return J

        return -1


def char_at(text, d):
    return ord(text[d])


class RabinKarp(SubstringSearch):
    patHash = None
    Q = 1573773197
    R = 256
    M = None
    RM = None

    def __init__(self, pat):
        h = 1
        self.M = len(pat)
        for i in range(1, self.M):
            h = (h * RabinKarp.R) % RabinKarp.Q

        self.RM = h

        self.patHash = self.hash(pat, self.M)

    def hash(self, text, M):
        h = 0
        for d in range(M):
            h = (h * RabinKarp.R + char_at(text, d)) % RabinKarp.Q
        return h

    def search_in(self, text):
        text_hash = self.hash(text, self.M)
        if text_hash == self.patHash:
            return 0
        for i in range(self.M, len(text)):
            text_hash = (text_hash + RabinKarp.Q - self.RM * char_at(text, i - self.M) % RabinKarp.Q) % RabinKarp.Q
            text_hash = (text_hash * RabinKarp.R + char_at(text, i)) % RabinKarp.Q
            if text_hash == self.patHash:
                return i - self.M + 1
        return -1


1			from abc import ABCMeta, abstractmethod
2
3
4			class SubstringSearch(object):
5			__metaclass__ = ABCMeta
6
7			@abstractmethod
8			def search_in(self, text):
9			pass
10
11
12			class BruteForceSubstringSearch(SubstringSearch):
13			def __init__(self, pattern):
14			self.pattern = pattern
15
16			def search_in(self, text):
17			n = len(text)
18
19			for i in range(n - len(self.pattern)):
20			J = i
21			for j in range(len(self.pattern)):
22			k = i + j
23			if text[k] != self.pattern[j]:
24			J = -1
25			break
26			if J != -1:
27			return J
28
29			return -1
30
31
32			def char_at(text, d):
33			return ord(text[d])
34
35
36			class RabinKarp(SubstringSearch):
37			patHash = None
38			Q = 1573773197
39			R = 256
40			M = None
41			RM = None
42
43			def __init__(self, pat):
44			h = 1
45			self.M = len(pat)
46			for i in range(1, self.M):
47			h = (h * RabinKarp.R) % RabinKarp.Q
48
49			self.RM = h
50
51			self.patHash = self.hash(pat, self.M)
52
53			def hash(self, text, M):
54			h = 0
55			for d in range(M):
56			h = (h * RabinKarp.R + char_at(text, d)) % RabinKarp.Q
57			return h
58
59			def search_in(self, text):
60			text_hash = self.hash(text, self.M)
61			if text_hash == self.patHash:
62			return 0
63			for i in range(self.M, len(text)):
64			text_hash = (text_hash + RabinKarp.Q - self.RM * char_at(text, i - self.M) % RabinKarp.Q) % RabinKarp.Q
65			text_hash = (text_hash * RabinKarp.R + char_at(text, i)) % RabinKarp.Q
66			if text_hash == self.patHash:
67			return i - self.M + 1
68			return -1
69

chen0040 / pyalgs

Push — master ( 999b46...f880e0 )

RabinKarp.search_in() A

Complexity

Size

Duplication

Importance

Duplication Side-by-Side

Filter issues like