scripts/fda.js at main · egoribragimov/scripts · GitHub

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
s = "ананас ананас ананас";
t = "ананас";
m = t.length
alph = new Array();
index = new Array();
//Определяем алфавит строки t
for (i = 0; i < m; i++)
    alph[t.charAt(i)] = 0;
//console.log(alph);
//В двумерном массиве del храним таблицу переходов
del = new Array(m + 1);
for (j = 0; j <= m; j++)
    del[j] = new Array();
//Инициализируем таблицу переходов
for (i in alph)
    del[0][i] = 0;
//Формируем таблицу переходов
for (j = 0; j < m; j++) {
    prev = del[j][t.charAt(j)];
    del[j][t.charAt(j)] = j + 1;
    for (i in alph)
        del[j + 1][i] = del[prev][i];
}

//Выводим таблицу переходов
out = '';
for (i in alph)
    out += i + ' ';
out += '\n';
for (j = 0; j <= m; j++) {
    for (i in alph)
        out += del[j][i] + " ";
    out += '\n';
}
console.log(out);

let state = 0;
for (i = 0; i < s.length; i++) {
    if (s.charAt(i) in alph)
        state = del[state][s.charAt(i)];
    else
        state = 0;
    if (state == m)
        //console.log(i - m + 1);
        index.push(i - m + 2);

}
console.log(index);