ref: bbb8f4aee6098856e9171bbbd12cb5e424a8ca2e
parent: 4813458af595305b5018c8f79b8f618e5c97189f
author: qwx <[email protected]>
date: Thu Dec 16 22:44:03 EST 2021
move string matchshit to its own dir
--- 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;
-}