Python: Monte Carlo Rabin-Karp search -

-

i trying implement monte carlo rabin-karp search in python. have far (random_prime function returns prime number less limit arguement given):

def search(pattern, text):  m = len(pattern) n = len(text) q = random_prime(m*n*n) r = (2^(m - 1)) % q f = [] x in range (0, n + 1):     f.append(0)  pfinger = 0 j in range(0, m):     f[0] = (2 * f[0]) + (int(text[j]) % q)     pfinger = (2 * pfinger) + (int(pattern[j]) % q)  = 0 while (i + m) < n:     if (f[i] == pfinger):         print "match @ position " + str(i)     f[i + 1] = (2 * (f[i] - (r * int(text[i])))) + (int(text[i + m]) % q)     += 1

the problem is, seems match first character or characters.

e.g. if call search('01', '101110001010101'), no match.

or if call search('1', '111110110100101') match.

or if call search('0', '0000001110001010101') matches position 5.

is there wrong code causing match incorrectly?

i'm no genius think found root of issue. in line r = (2^(m - 1)) % q , knowledge ^ not correct character creating exponential function. correct character use in python ** such r = (2**(m - 1)) % q. search should print positions except last. can fixed changing < n <= n in line (while (i+m)< n:)

you code print positions although receive index error occurs once positions have been identified. can solved ignoring error once occurs.

try:

   f[i + 1] = (2 * (f[i] - (r * int(text[i])))) + (int(text[i + m]) % q)     += 1

except:

   break

Comments

Post a Comment

Popular posts from this blog

javascript - Chart.js (Radar Chart) different scaleLineColor for each scaleLine -

-
Image
i try , create radar chart using chart.js has various colours each scaleline, or coloured between scalelines. wondering if possible? from: to: i have working graph, though there doesn't seem method change individual scale lines. kind regards leigh you can extend radar chart type this, so chart.types.radar.extend({ name: "radaralt", initialize: function (data) { chart.types.radar.prototype.initialize.apply(this, arguments); var originalscaledraw = this.scale.draw; var ctx = this.chart.ctx; this.scale.draw = function () { var linewidth = this.linewidth; // bypasses line drawing in originalscaledraw this.linewidth = linewidth; originalscaledraw.apply(this, arguments); ctx.linewidth = this.linewidth; var scale = this; // draw chart.helpers.each(scale.ylabels, function (label, index) { // color of ...
Read more

apache - Error with PHP mail(): Multiple or malformed newlines found in additional_header -

-
suddenly have started receiving above error without changes having been made script. host 1and1 (i know...) the script still works fine on different server, , suspicion there must have been server config change has lead this, although hosts plead ignorance. there's no information on above error @ in google can find - have ideas? server running apache if helps. had similar problem. came out of blue. no php code changed. what changed: php upgraded 5.5.25-1 5.5.26. a security risk in php mail() function has been fixed , newlines in additional_headers allowed no more. because newlines mean: starts email message (and surely don't want inject newlines through headers followed evil message). what have worked fine, e.g. having newlines after headers or passing whole message additional_headers , function no more. solution : sanitize headers. no multiple newlines in additional_headers argument. these count "multiple or malformed newlines":...
Read more

java - Android – MapFragment overlay button shadow, just like MyLocation button -

-
Image
i'm struggling add shadow custom overlay button on google map. goal make custom button google's mylocation button. here's how app looks now: layout.xml <relativelayout xmlns:android="http://schemas.android.com/apk/res/android" xmlns:tools="http://schemas.android.com/tools" xmlns:map="http://schemas.android.com/apk/res-auto" android:layout_height="match_parent" android:layout_width="match_parent" style="@style/apptheme"> <fragment android:layout_width="match_parent" android:layout_height="match_parent" android:id="@+id/map" tools:context=".mapsactivity" android:name="com.google.android.gms.maps.supportmapfragment" android:layout_alignparentend="true" android:layout_alignparentstart="true" android:layout_alignparentbottom="true" ...
Read more