Lines Matching defs:table
40 /* Allocate the table. */
41 size_t *table = (size_t *) nmalloca (m, sizeof (size_t));
42 if (table == NULL)
44 /* Fill the table.
46 0 < table[i] <= i is defined such that
47 forall 0 < x < table[i]: needle[x..i-1] != needle[0..i-1-x],
48 and table[i] is as large as possible with this property.
51 If table[i] < i,
52 needle[table[i]..i-1] = needle[0..i-1-table[i]].
57 forall 0 <= x < table[i]: rhaystack[x..x+m-1] != needle[0..m-1].
58 table[0] remains uninitialized. */
63 table[1] = 1;
68 /* Here: j = i-1 - table[i-1].
70 for x < table[i-1], by induction.
81 /* Set table[i] := i-1-j. */
82 table[i] = i - ++j;
91 table[i] = i;
95 for i-1-j < x < i-1-j+table[j], because for these x:
98 != needle[0..j-1-(x-(i-1-j))] (by definition of table[j])
102 needle[i-1-j+table[j]..i-2]
103 = needle[table[j]..j-1]
104 = needle[0..j-1-table[j]] (by definition of table[j]). */
105 j = j - table[j];
107 /* Here: j = i - table[i]. */
111 /* Search, using the table to accelerate the processing. */
138 rhaystack += table[j];
139 j -= table[j];
149 freea (table);