Finite Automata

gistfile1.txt

// ∅ (∈)=q0
// ∅ (wa) = δ((∅(w), a) for w ∈ ∑*, a∈ ∑)
let NO_OF_CHARS = 256;
/* This function builds the TF table
    which represents Finite Automata for a
    given pattern */
function computeTransFunc(pat, M, TF) {
    let i, lps = 0, x;
    // Fill entries in first row
    for (x = 0; x < NO_OF_CHARS; x++) {
        TF[0][x] = 0;
    }
    TF[0][pat[0].charCodeAt(0)] = 1;
    // Fill entries in other rows
    for (i = 1; i < M; i++) {
        // Copy values from row at index lps
        for (x = 0; x < NO_OF_CHARS; x++) {
            TF[i][x] = TF[lps][x];
        }
        // Update the entry corresponding to this character
        TF[i][pat[i].charCodeAt(0)] = i + 1;
        // Update lps for next row to be filled
        if (i < M) {
            lps = TF[lps][pat[i].charCodeAt(0)];
        }
    }
}
/* Prints all occurrences of pat in txt */
function search(pat, txt) {
    let M = pat.length;
    let N = txt.length;
    let TF = new Array(M + 1);
    for (let i = 0; i < M + 1; i++) {
        TF[i] = new Array(NO_OF_CHARS);
        for (let j = 0; j < NO_OF_CHARS; j++) {
            TF[i][j] = 0;
        }
    }
    computeTransFunc(pat, M, TF);
    // process text over FA.
    let i, j = 0;
    for (i = 0; i < N; i++) {
        j = TF[j][txt[i].charCodeAt(0)];
        if (j == M) {
            console.log("match @ " +
                (i - M + 1) + " ");
        }
    }
}
/*-----------
--------*/
/* Driver code */
let txt = "GEEKS FOR GEEKS".split("");
let pat = "GEEKS".split("");
search(pat, txt);