miao.string.not_so_naive source code

1 module miao..string.not_so_naive;
2 
3 /*!
4 Main features
5     preprocessing phase in constant time and space;
6     searching phase in O(nm) time complexity;
7     slightly (by coefficient) sub-linear in the average case.
8 
9 Description
10     During the searching phase of the Not So Naive algorithm the character comparisons are made with the pattern positions in the following order 1, 2, ... , m-2, m-1, 0.
11     For each attempt where the window is positioned on the text factor y[j .. j+m-1]: if x[0]=x[1] and x[1] neq y[j+1] of if x[0] neq x[1] and x[1]=y[j+1] the pattern is shifted by 2 positions at the end of the attempt and by 1 otherwise.
12     Thus the preprocessing phase can be done in constant time and space. The searching phase of the Not So Naive algorithm has a quadratic worst case but it is slightly (by coefficient) sub-linear in the average case.
13 */
14 
15 @trusted:
16 
17 import miao.common.check;
18 import miao.common.util;
19 
20 struct Not_so_naive_searcher(PatRange, CorpusRange = PatRange) 
21     if (isValidParam!(PatRange, CorpusRange)) {
22 public:
23     this(in PatRange pattern)
24     {
25         pattern_ = pattern;
26         if (pattern_.length >= 2) {
27             if (pattern_[0] == pattern_[1]) {
28                 skip_ = 2;
29                 slide_ = 1;
30             }
31             else {
32                 skip_ = 1;
33                 slide_ = 2;
34             }
35         }
36     }
37 
38     int search(in CorpusRange corpus) const
39     out(result) {
40             assert(result == -1 || (0 <= result && result < corpus.length));
41     }
42 	body {
43 		if (corpus.length == 0 || pattern_.length == 0) return -1;
44 		if (corpus.length < pattern_.length) return -1;
45         if (pattern_.length == 1) {
46             return pattern_[0] == corpus[0]? 0: -1;
47         }
48 		return search_(corpus);
49 	}
50 
51 private:
52     int search_(in CorpusRange corpus) const
53     in {
54         assert(corpus.length >= 2);
55         assert(pattern_.length >= 2);
56     }
57     body {
58         const cmp_len = corpus.length - pattern_.length;
59 
60         for (auto window_pos = 0; window_pos <= cmp_len; ) {
61             const window = corpus[window_pos .. window_pos + pattern_.length];
62             if (window[1] != pattern_[1]) {
63                 window_pos += skip_;
64             }
65             else {
66                 if (window == pattern_) return window_pos;
67                 window_pos += slide_;
68             }
69         }
70 
71         return -1;
72     }
73     
74 private:
75     const PatRange pattern_;
76     immutable uint skip_;
77     immutable uint slide_;
78 }
79 
80 alias not_so_naive_search = GenerateFunction!Not_so_naive_searcher;
81 
82 unittest {
83     import miao.string.test;
84     
85     testAll!(Not_so_naive_searcher, not_so_naive_search)();
86 }