kactl
kactl copied to clipboard
Add finite state automaton to KMP
// Needs failure function of kmp to work,
// automaton builds a string recognizer
// Input : String `s`, First starting character `ch`, character size `charSize` (numbers of available characters)
// Output : A Finite state machine, initial at 0, accepting state at sz(s).
// Time complexity, Space Complexity: O(charSize * sz(S))
vvi automaton(string s, char ch, int charSize) {
s += '$'; vi ff = pi(s);
vvi aut(sz(s), vi(charSize));
rep(i, 0, sz(s)) {
rep(c, 0, charSize) {
aut[i][c] = ((i > 0 && ch + c != s[i]) ? aut[ff[i - 1]][c] : (i + (ch + c == s[i])));
}
}
return aut;
}