shithub: asif

Info  •  Files  •  Log

move string matchshit to its own dir

diff: cannot open b/match//null: file does not exist: 'b/match//null'

--- a/kmp.c

+++ /dev/null

@@ -1,80 +1,0 @@

-#include <u.h>

-#include <libc.h>

-#include "asif.h"

-

-/* morris-pratt exact string search of a word W within a text S with W preprocessing */

-

-static int *

-mpjumptab(String W)

-{

-	int i, j, *T;

-

-	T = emalloc(W.n + 1);

-	T[0] = -1;

-	for(i=-1, j=0; j<W.n;){

-		while(i > -1 && W.s[i] != W.s[j])

-			i = T[i];

-		T[++j] = ++i;

-	}

-	return T;

-}

-

-/* ordinary knuth-morris-pratt exact string search of a word W within a text S

- * with W preprocessing */

-

-static int *

-kmpjumptab(String W)

-{

-	int i, j, *T;

-

-	T = emalloc(W.n + 1);

-	T[0] = -1;

-	for(i=-1, j=0; j<W.n;){

-		while(i > -1 && W.s[i] != W.s[j])

-			i = T[i];

-		i++;

-		j++;

-		if(W.s[i] == W.s[j])

-			T[j] = T[i];

-		else

-			T[j] = i;

-	}

-	return T;

-}

-

-static VArray *

-search(String S, String W, int*(*tabfn)(String))

-{

-	int n, i, j, *T;

-	VArray *v;

-

-	n = S.n - W.n + 1;

-	if(n <= 0)

-		return nil;

-	v = valloc(n, sizeof(int));

-	T = tabfn(W);

-	for(i=j=0; j<W.n;){

-		while(i > -1 && W.s[i] != S.s[j])

-			i = T[i];

-		i++, j++;

-		if(i >= W.n){

-			n = j - i;

-			vinsert(v, (void*)&n);

-			i = T[i];

-		}

-	}

-	free(T);

-	return v;

-}

-

-VArray *

-morrispratt(String S, String W)

-{

-	return search(S, W, mpjumptab);

-}

-

-VArray *

-knuthmorrispratt(String S, String W)

-{

-	return search(S, W, kmpjumptab);

-}

--- /dev/null

+++ b/match/kmp.c

@@ -1,0 +1,80 @@

+#include <u.h>

+#include <libc.h>

+#include "asif.h"

+

+/* morris-pratt exact string search of a word W within a text S with W preprocessing */

+

+static int *

+mpjumptab(String W)

+{

+	int i, j, *T;

+

+	T = emalloc(W.n + 1);

+	T[0] = -1;

+	for(i=-1, j=0; j<W.n;){

+		while(i > -1 && W.s[i] != W.s[j])

+			i = T[i];

+		T[++j] = ++i;

+	}

+	return T;

+}

+

+/* ordinary knuth-morris-pratt exact string search of a word W within a text S

+ * with W preprocessing */

+

+static int *

+kmpjumptab(String W)

+{

+	int i, j, *T;

+

+	T = emalloc(W.n + 1);

+	T[0] = -1;

+	for(i=-1, j=0; j<W.n;){

+		while(i > -1 && W.s[i] != W.s[j])

+			i = T[i];

+		i++;

+		j++;

+		if(W.s[i] == W.s[j])

+			T[j] = T[i];

+		else

+			T[j] = i;

+	}

+	return T;

+}

+

+static VArray *

+search(String S, String W, int*(*tabfn)(String))

+{

+	int n, i, j, *T;

+	VArray *v;

+

+	n = S.n - W.n + 1;

+	if(n <= 0)

+		return nil;

+	v = valloc(n, sizeof(int));

+	T = tabfn(W);

+	for(i=j=0; j<W.n;){

+		while(i > -1 && W.s[i] != S.s[j])

+			i = T[i];

+		i++, j++;

+		if(i >= W.n){

+			n = j - i;

+			vinsert(v, (void*)&n);

+			i = T[i];

+		}

+	}

+	free(T);

+	return v;

+}

+

+VArray *

+morrispratt(String S, String W)

+{

+	return search(S, W, mpjumptab);

+}

+

+VArray *

+knuthmorrispratt(String S, String W)

+{

+	return search(S, W, kmpjumptab);

+}

--- /dev/null

+++ b/match/rabinkarp.c

@@ -1,0 +1,77 @@

+#include <u.h>

+#include <libc.h>

+#include "asif.h"

+

+/* rabin-karp for single pattern matching

+ * d: base

+ * q: modulo factor

+ * D: multiplication factor in the recurrence formula:

+ *	h = (d * (h - D * S[i]) + S[i+M]) % q

+ *	D = d ** (M-1) % q

+ */

+

+/* http://monge.univ-mlv.fr/~lecroq/string/node5.html:

+ * fast specialized version for 8-byte values, using the full range of a 32bit integer,

+ * avoiding divisions, simplifying the precalculation of D and reducing most operations

+ * to bit shifts.

+ * assumed d = 2, q = 2³³

+ * d*q < 2³³ not necessary since no intermediate values are stored

+ *

+ * some small modifications compared to the site to hopefully correct some issues:

+ * - avoid out of bounds on last iteration

+ * - calculate D in one step and avoid shifting beyond 32 bits

+ */

+VArray *

+rabinkarp8(String W, String S)

+{

+	int i, n, ds, hw, hs;

+	VArray *v;

+

+	n = S.n - W.n + 1;

+	if(n <= 0)

+		return nil;

+	v = valloc(n, sizeof(int));

+	ds = W.n - 1 & 0x1f;

+	hw = 0;

+	hs = 0;

+	for(i=0; i<W.n; i++){

+		hw = W.s[i] + (hw << 1);

+		hs = S.s[i] + (hs << 1);

+	}

+	for(i=0, n--;; i++){

+		if(hw == hs && memcmp(W.s, S.s+i, W.n) == 0)

+			vinsert(v, (void*)&i);

+		if(i >= n)

+			break;

+		hs = S.s[i+W.n] + (hs - (S.s[i] << ds) << 1);

+	}

+	return v;

+}

+

+/* general algorithm */

+VArray *

+rabinkarp(String W, String S, int d, int q)

+{

+	int i, n, D, hw, hs;

+	VArray *v;

+

+	n = S.n - W.n + 1;

+	if(n <= 0)

+		return nil;

+	v = valloc(n, sizeof(int));

+	D = modpow(d, W.n - 1, q);

+	hw = 0;

+	hs = 0;

+	for(i=0; i<W.n; i++){

+		hw = (W.s[i] + d * hw) % q;

+		hs = (S.s[i] + d * hs) % q;

+	}

+	for(i=0, n--;; i++){

+		if(hw == hs && memcmp(W.s, S.s+i, W.n) == 0)

+			vinsert(v, (void*)&i);

+		if(i >= n)

+			break;

+		hs = (S.s[i+W.n] + d * (hs - D * S.s[i])) % q;

+	}

+	return v;

+}

--- /dev/null

+++ b/match/strnaive.c

@@ -1,0 +1,20 @@

+#include <u.h>

+#include <libc.h>

+#include "asif.h"

+

+/* naive exact string search of a word within a text */

+VArray *

+naivestrfind(String S, String W)

+{

+	int i, n;

+	VArray *v;

+

+	n = S.n - W.n + 1;

+	if(n <= 0)

+		return nil;

+	v = valloc(n, sizeof(int));

+	for(i=0; i<n; i++)

+		if(strcmp(S.s+i, W.s) == 0)

+			vinsert(v, (void*)&i);

+	return v;

+}

--- a/rabinkarp.c

+++ /dev/null

@@ -1,77 +1,0 @@

-#include <u.h>

-#include <libc.h>

-#include "asif.h"

-

-/* rabin-karp for single pattern matching

- * d: base

- * q: modulo factor

- * D: multiplication factor in the recurrence formula:

- *	h = (d * (h - D * S[i]) + S[i+M]) % q

- *	D = d ** (M-1) % q

- */

-

-/* http://monge.univ-mlv.fr/~lecroq/string/node5.html:

- * fast specialized version for 8-byte values, using the full range of a 32bit integer,

- * avoiding divisions, simplifying the precalculation of D and reducing most operations

- * to bit shifts.

- * assumed d = 2, q = 2³³

- * d*q < 2³³ not necessary since no intermediate values are stored

- *

- * some small modifications compared to the site to hopefully correct some issues:

- * - avoid out of bounds on last iteration

- * - calculate D in one step and avoid shifting beyond 32 bits

- */

-VArray *

-rabinkarp8(String W, String S)

-{

-	int i, n, ds, hw, hs;

-	VArray *v;

-

-	n = S.n - W.n + 1;

-	if(n <= 0)

-		return nil;

-	v = valloc(n, sizeof(int));

-	ds = W.n - 1 & 0x1f;

-	hw = 0;

-	hs = 0;

-	for(i=0; i<W.n; i++){

-		hw = W.s[i] + (hw << 1);

-		hs = S.s[i] + (hs << 1);

-	}

-	for(i=0, n--;; i++){

-		if(hw == hs && memcmp(W.s, S.s+i, W.n) == 0)

-			vinsert(v, (void*)&i);

-		if(i >= n)

-			break;

-		hs = S.s[i+W.n] + (hs - (S.s[i] << ds) << 1);

-	}

-	return v;

-}

-

-/* general algorithm */

-VArray *

-rabinkarp(String W, String S, int d, int q)

-{

-	int i, n, D, hw, hs;

-	VArray *v;

-

-	n = S.n - W.n + 1;

-	if(n <= 0)

-		return nil;

-	v = valloc(n, sizeof(int));

-	D = modpow(d, W.n - 1, q);

-	hw = 0;

-	hs = 0;

-	for(i=0; i<W.n; i++){

-		hw = (W.s[i] + d * hw) % q;

-		hs = (S.s[i] + d * hs) % q;

-	}

-	for(i=0, n--;; i++){

-		if(hw == hs && memcmp(W.s, S.s+i, W.n) == 0)

-			vinsert(v, (void*)&i);

-		if(i >= n)

-			break;

-		hs = (S.s[i+W.n] + d * (hs - D * S.s[i])) % q;

-	}

-	return v;

-}

--- a/strnaive.c

+++ /dev/null

@@ -1,20 +1,0 @@

-#include <u.h>

-#include <libc.h>

-#include "asif.h"

-

-/* naive exact string search of a word within a text */

-VArray *

-naivestrfind(String S, String W)

-{

-	int i, n;

-	VArray *v;

-

-	n = S.n - W.n + 1;

-	if(n <= 0)

-		return nil;

-	v = valloc(n, sizeof(int));

-	for(i=0; i<n; i++)

-		if(strcmp(S.s+i, W.s) == 0)

-			vinsert(v, (void*)&i);

-	return v;

-}