shithub: asif

Download patch

ref: 44dfc2ed7f45a337358e8b113aa408a7cc2975a7
parent: 049ac5456df23da6d3b6d22d1c7bedc99d820c94
author: qwx <qwx@sciops.net>
date: Sat Aug 22 18:13:02 EDT 2020 

kmp: add morris-pratt search


--- a/asif.h
+++ b/asif.h
@@ -17,7 +17,8 @@
 VArray*	valloc(ulong, int);
 
 VArray*	naivestrfind(String, String);
-VArray*	kmpstrfind(String, String);
+VArray*	morrispratt(String, String);
+VArray*	knuthmorrispratt(String, String);
 
 typedef struct Pairheap Pairheap;
 struct Pairheap{
--- a/kmp.c
+++ b/kmp.c
@@ -2,11 +2,28 @@
 #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 *
-jumptab(String W)
+kmpjumptab(String W)
 {
 	int i, j, *T;
 
@@ -25,8 +42,8 @@
 	return T;
 }
 
-VArray *
-kmpstrfind(String S, String W)
+static VArray *
+search(String S, String W, int*(*tabfn)(String))
 {
 	int n, i, j, *T;
 	VArray *v;
@@ -34,7 +51,7 @@
 	if(S.n < W.n)
 		return nil;
 	v = valloc(n, sizeof(int));
-	T = jumptab(W);
+	T = tabfn(W);
 	for(i=j=0; j<W.n;){
 		while(i > -1 && W.s[i] != S.s[j])
 			i = T[i];
@@ -47,4 +64,16 @@
 	}
 	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);
 }