Алгоритм Ахо-Корасика

Пожалуйста, помогите мне найти ошибки в этом коде. Я написал простую программу, которая добавляет n строк в три по алгоритму Aho-Corasick, но он не работает правильно. Сбой после ввода строк. Что не так с этим кодом?

#include <cstdlib>
#include <iostream>
#include <vector>
#define ALPHABET 26

using namespace std;

struct item
{
int next[ALPHABET];
int leaf;
item()
{
for (int i = 0; i < ALPHABET; i++)
next[i] = -1;
leaf = 0;
}
};

vector <item> trie;

int add_string(string &s)
{
int z = 0;
item temp;
for (int i = 0; i < s.length(); i++)
{
char c = s[i] - 'a';
if (trie[z].next[c] == -1)
{
trie[z].next[c] = trie.size();
trie.push_back(temp);}
z = trie[z].next[c];
}
trie[z].leaf = true;
}
}

int main(int argc, char *argv[])
{
int n;
cin >> n;
string s[n];
for (int i = 0; i < n; i++)
cin >> s[i];
for (int i = 0; i < n; i++)
add_string(s[i]);
system("PAUSE");
return EXIT_SUCCESS;
}

-1

Решение

Я ничего не знаю об алгоритме, поэтому понятия не имею, работает ли он правильно. Тем не менее, просто на основе запуска вашего кода через GDB, вы должны начать по крайней мере с одним элементом в вашем trie вектор. Вы можете сделать это, написав

vector <item> trie(1);

где 1 показывает, сколько элементов должен начинать вектор. С этим изменением код работает нормально (но я не знаю, правильно ли он выполняет алгоритм).

0

Другие решения

Других решений пока нет …