Sum of longest prefix-suffix strings

gistfile1.js

/**
 * Finding sum of longest prefix-suffix strings in a string S
 *
 * A prefix string of string S is S[0..i]
 * A suffix string of string S is S[i..n-1] (n = S's length)
 *
 * Longest prefix-suffix of a string is max value k where
 * suffix[0..k-1] == prefix[0..k-1]
 *
 * @param  {[string]} S [Input string]
 * @return {[number]}   [Sum of longest prefix-suffix strings]
 */
function sumOfPrefixSuffix(s) {
  // Init array Z of length S.length
  var Z = Array.apply(null, Array(s.length)).map(function() {
    return 0;
  });

  /**
   * [L, R] is the longest range which satisfies
   * 1 <= L <= i <= R and S[L,R] is a prefix
   */
  var L = R = -1;
  for (var i = 1; i < s.length; i++) {
    // Find new range which contain i
    if (i > R) {
      L = R = i;
      while (s[R - L] === s[R] && R < s.length) R++;
      Z[i] = R - L;
      // since s[R] is not a match with current R
      R--;
    } else {
      // S[L..i] match with S[0..k]
      var k = i - L;

      /**
       * since S[k..R-L] match with S[i..R]
       * then if Z[k] < R-i+1, the prefix-suffix
       * S[i] should not have longer length than Z[k]
       */
      if (Z[k] < R - i + 1) {
        Z[i] = Z[k];
      } else {
        /**
         * since S[k..R-L] match with S[i..R] and Z[k] > R-i+1
         * then R-i+1 position is match with S's prefix, thus we
         * just need to expand the substring from current R
         */
        L = i;
        while (s[R - L] === s[R] && R < s.length) R++;
        Z[i] = R - L;
        R--;
      }
    }
  }

  return Z.reduce(function(total, value) {
    return total + value;
  }, s.length);
}

more consice

function sumOfPrefixSuffix(s) {
  var Z = Array.apply(null, Array(s.length)).map(function() {
    return 0;
  });

  var L = R = -1;
  for (var i = 1; i < s.length; i++) {
    var k = i < R ? Math.min(Z[i - L], R - i) : 0;
    while (i + k < s.length && s[i + k] === s[k]) k++;
    Z[i] = k;
    if (i + k > R) {
      L = i;
      R = i + k;
    }
  }

  return Z.reduce(function(total, value) {
    return total + value;
  }, s.length);
}

Ref

[1] http://codeforces.com/blog/entry/3107
[2] http://www.utdallas.edu/~besp/demo/John2010/z-algorithm.htm