function kmp()

in core/src/main/resources/org/apache/karaf/webconsole/core/behavior/dracula/dracula_algorithms.js [466:504]

• 10 lines of code
• 7 McCabe index (conditional complexity)

function kmp(p, t) {

    /**
     * PREFIX, OVERLAP or FALIURE function for KMP. Computes how many iterations
     * the algorithm can skip after a mismatch.
     *
     * @input p - pattern (string)
     * @result array of skippable iterations
     */
    function prefix(p) {
        /* pi contains the computed skip marks */
        var pi = [0], k = 0;
        for(q = 1; q < p.length; q++) {
            while(k > 0 && (p.charAt(k) != p.charAt(q)))
                k = pi[k-1];
            
            (p.charAt(k) == p.charAt(q)) && k++;
            
            pi[q] = k;
        }
        return pi;
    }
    
    /* The actual KMP algorithm starts here. */
    
    var pi = prefix(p), q = 0, result = [];
    
    for(var i = 0; i < t.length; i++) {
        /* jump forward as long as the character doesn't match */
        while((q > 0) && (p.charAt(q) != t.charAt(i)))
            q = pi[q];
        
        (p.charAt(q) == t.charAt(i)) && q++;
        
        (q == p.length) && result.push(i - p.length) && (q = pi[q]);
    }
    
    return result;
}