blob: e097b4283044ea6fbc75136ca1275e4a3fdb19e0 (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
|
#include <u.h>
#include <base/memory.h>
#include <base/string.h>
char *
str·efind(char *h, char *e, char *n)
{
char *s, *ih, *in;
intptr i, sum, sz;
if(!n || !n[0])
return h;
if(!h || !h[0] || h > e)
return nil;
/* two way string matching */
/* align first characters */
if(!(s = str·findc(h, n[0])))
return nil;
ih = s+1;
in = n+1;
i = 1, sum = 0;
while(*ih && *in && ih != e){
sum += *ih;
sum -= *in;
i &= (*ih++ == *in++);
}
if(*in) /* needle is larger than haystack! */
return nil;
else if(i) /* found match */
return s;
/* no hit: loop for remainder of haystack
* if prefix sum ever falls to zero, we have equal hashes
* compare! */
sz = in - n - 1;
for(; *ih && ih != e; ih++){
sum -= *s++; /* sub the last character, advance the location on haystack */
sum += *ih; /* add the next character */
if(sum == 0 && mem·compare(s, sz, n)==0)
return s;
}
return nil;
}
|