StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

POFinding cycle in Aho-Corasick automaton
text
Body
copied!<p>I'am facing a problem which should be solved using Aho-Corasick automaton. I'am given a set of words (composed with '0' or '1') - patterns and I must decide if it is possible to create infinite text, which wouldn't contain any of given patterns. I think, the solution is to create Aho-Corasick automaton and search for a cycle without matching states, but I'm not able to propose a good way to do that. I thought of searching the states graph using DFS, but I'm not sure if it will work and I have an implementation problem - let's assume, that we are in a state, which has an '1' edge - but state pointed by that edge is marked as matching - so we cannot use that edge, we can try fail link (current state doesn't have '0' edge) - but we must also remember, that we could not go with '1' edge from state pointed by fail link of the current one.</p> <p>Could anyone correct me and show me how to do that? I've written Aho-Corasick in C++ and I'am sure it works - I also understand the entire algorithm.</p> <p>Here is the base code:</p> <pre><code>class AhoCorasick { static const int ALPHABET_SIZE = 2; struct State { State* edge[ALPHABET_SIZE]; State* fail; State* longestMatchingSuffix; //Vector used to remember which pattern matches in this state. vector< int > matching; short color; State() { for(int i = 0; i < ALPHABET_SIZE; ++i) edge[i] = 0; color = 0; } ~State() { for(int i = 0; i < ALPHABET_SIZE; ++i) { delete edge[i]; } } }; private: State root; vector< int > lenOfPattern; bool isFailComputed; //Helper function used to traverse state graph. State* move(State* curr, char letter) { while(curr != &root && curr->edge[letter] == 0) { curr = curr->fail; } if(curr->edge[letter] != 0) curr = curr->edge[letter]; return curr; } //Function which computes fail links and longestMatchingSuffix. void computeFailLink() { queue< State* > Q; root.fail = root.longestMatchingSuffix = 0; for(int i = 0; i < ALPHABET_SIZE; ++i) { if(root.edge[i] != 0) { Q.push(root.edge[i]); root.edge[i]->fail = &root; } } while(!Q.empty()) { State* curr = Q.front(); Q.pop(); if(!curr->fail->matching.empty()) { curr->longestMatchingSuffix = curr->fail; } else { curr->longestMatchingSuffix = curr->fail->longestMatchingSuffix; } for(int i = 0; i < ALPHABET_SIZE; ++i) { if(curr->edge[i] != 0) { Q.push(curr->edge[i]); State* state = curr->fail; state = move(state, i); curr->edge[i]->fail = state; } } } isFailComputed = true; } public: AhoCorasick() { isFailComputed = false; } //Add pattern to automaton. //pattern - pointer to pattern, which will be added //fun - function which will be used to transform character to 0-based index. void addPattern(const char* const pattern, int (*fun) (const char *)) { isFailComputed = false; int len = strlen(pattern); State* curr = &root; const char* pat = pattern; for(; *pat; ++pat) { char tmpPat = fun(pat); if(curr->edge[tmpPat] == 0) { curr = curr->edge[tmpPat] = new State; } else { curr = curr->edge[tmpPat]; } } lenOfPattern.push_back(len); curr->matching.push_back(lenOfPattern.size() - 1); } }; int alphabet01(const char * c) { return *c - '0'; } </code></pre>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload