Simon algorithm (original) (raw)

The main drawback of the search with the minimal A(x) (see Deterministic Finite Automaton) is the size of the automaton: O(m).

Simon noticed that there are only a few significant edges in A(x) ;

they are:

	the forward edges going from the prefix of x of length k to the prefix of length k+1 for 0 k < m. There are exactly m such edges;

	the backward edges going from the prefix of x of length k to a smaller non-zero length prefix. The number of such edges is bounded by m.

The other edges are leading to the initial state and can then be deduced. Thus the number of significant edges is bounded by 2_m_. Then for each state of the automaton it is only necessary to store the list of its significant outgoing edges.

Each state is represented by the length of its associated prefix minus 1 in order that each edge leading to state i, with -1 i _m_-1 is labelled by _x_[_i_] thus it is not necessary to store the labels of the edges. The forward edges can be easily deduced from the pattern, thus they are not stored. It only remains to store the significant backward edges.

We use a table L, of size _m_-2, of linked lists. The element _L_[_i_] gives the list of the targets of the edges starting from state i. In order to avoid to store the list for the state _m_-1, during the computation of this table L, the integer is computed such that +1 is the length of the longest border of x.

The preprocessing phase of the Simon algorithm consists in computing the table L and the integer . It can be done in O(m) space and time complexity.

The searching phase is analogous to the one of the search with an automaton. When an occurrence of the pattern is found, the current state is updated with the state . This phase can be performed in O(m+n) time. The Simon algorithm performs at most 2_n_-1 text character comparisons during the searching phase. The delay (maximal number of comparisons for a single text character) is bounded by min{1+log2(m), }.

The description of a linked list List can be found in the introduction section implementation.

int getTransition(char *x, int m, int p, List L[], char c) { List cell;

if (p < m - 1 && x[p + 1] == c) return(p + 1); else if (p > -1) { cell = L[p]; while (cell != NULL) if (x[cell->element] == c) return(cell->element); else cell = cell->next; return(-1); } else return(-1); }

void setTransition(int p, int q, List L[]) { List cell;

cell = (List)malloc(sizeof(struct _cell)); if (cell == NULL) error("SIMON/setTransition"); cell->element = q; cell->next = L[p]; L[p] = cell; }

int preSimon(char *x, int m, List L[]) { int i, k, ell; List cell;

memset(L, NULL, (m - 2)*sizeof(List)); ell = -1; for (i = 1; i < m; ++i) { k = ell; cell = (ell == -1 ? NULL : L[k]); ell = -1; if (x[i] == x[k + 1]) ell = k + 1; else setTransition(i - 1, k + 1, L); while (cell != NULL) { k = cell->element; if (x[i] == x[k]) ell = k; else setTransition(i - 1, k, L); cell = cell->next; } } return(ell); }

void SIMON(char *x, int m, char *y, int n) { int j, ell, state; List L[XSIZE];

/* Preprocessing */ ell = preSimon(x, m, L);

/* Searching */ for (state = -1, j = 0; j < n; ++j) { state = getTransition(x, m, state, L, y[j]); if (state >= m - 1) { OUTPUT(j - m + 1); state = ell; } } }

The states are labelled by the length of the prefix they are associated with minus 1.