First of all, I'm sorry if I write a lot, I tried to summarize my research so that everyone can understand.
R. Baeza-Yates and M. Regnier published in 1990 a new algorithm for finding the two-dimensional mm template in two-dimensional nn-text. The publication is very well written and understandable for beginners like me, the algorithm is described in pseudocode, and I was able to successfully implement it.
One part of the BYR algorithm requires the Aho-Corasick algorithm. This allows you to search for occurrences of several keywords in the text text. However, they also say that this part of their algorithm can be significantly improved using the Aho-Korasik algorithm, but the Commentz-Walter algorithm (based on the Boyer-Moore algorithm, and not the Knut-Morris-Pratt algorithm). They invoke an alternative to the Commentz-Walter algorithm, an alternative that they themselves have developed. This is described and explained in their previous publication (see chapter 4).
That is where my problem is. As I said, the algorithm goes through the text and checks if it contains a word from a set of keywords. The words are located upside down and placed in a tree. To be effective, it is sometimes necessary to skip a few letters when he knows that no match has been found.
To determine the number of characters that can be skipped, two tables must be calculated dand dd. Then the algorithm is very simple:
The algorithm works as follows:
- We align the trie root with the position m in the text, and we begin to match the text from right to left, following the corresponding path in the trie.
- If a match is found (final node), we print the index of the corresponding row.
- trie , , node ( dd), d [x], x - , trie.
- .
, , dd. . - . :
pi - , j - , pi [j] node , . node dd (node). L - , mi - pi.
. W. Rytter. , , , , .
dd ( D) :
, .
, , ++:
int pattern[] = { 1, 2, 3, 1 }; /* I use int instead of char, simpler */
const int n = sizeof(pattern) / 4;
int D[n];
int f[n];
int j = n;
int t = n + 1;
for (int k = 1; k <= n; k++){
D[k-1] = 2 * n - k;
}
while (j > 0) {
f[j-1] = t;
while (t <= n) {
if (pattern[j-1] != pattern[t-1]) {
D[t-1] = min(D[t-1], n - j);
t = f[t-1];
}
else {
break;
}
}
t = t - 1;
j = j - 1;
}
int f1[n];
int q = t;
t = n + 1 - q;
int q1 = 1;
int j1 = 1;
int t1 = 0;
while (j1 <= t) {
f1[j1 - 1] = t1;
while (t1 >= 1) {
if (pattern[j1 - 1] != pattern[t1 - 1]) {
t1 = f1[t1 - 1];
}
else {
break;
}
}
t1 = t1 + 1;
j1 = j1 + 1;
}
while (q < n) {
for (int k = q1; k <= q; k++) {
D[k - 1] = min(D[k - 1], n + q - k);
}
q1 = q + 1;
q = q + t - f1[t - 1];
t = f1[t - 1];
}
for (int i = 0; i < n; i++)
{
cout << D[i] << " ";
}
, , , , dd, Baeza-Yates Régnier. , , , .
, , dd, , , , me d dd.