kyle-Snippet: Longset Palindromic Substring

palindrome.js

// Write a function that finds the longest palindromic substring in a string.
// ex: findLongstPal('affaptbbcracecarf') returns 'racecar'

// O(N^2)
function findLongestPalOld(input){
    var longestPal = "";
    var len = input.length;

    var isPalindrome = function(palindrome){
        return palindrome.split('').reverse().join('') == palindrome;
    }

    for (var i =0; i < len; i++) {
        for (var j=len -1; j>=i; j--){
            var supposedPal = input.substring(i,j);
            if (supposedPal.length > 3 && isPalindrome(supposedPal)){
                longestPal = longestPal.length > supposedPal.length ? longestPal : supposedPal;
            }
        }
    }

    return longestPal;
}
// O(N)
// This one is based on some work that smarter people have done. If anything
// I learned more about the Big O notation an how to move towards linear time and space
// functions.

function findLongestPalNew(seq){
	var seqLen = seq.length,
		l = [],
		center = 0,
		longestPal = '',
		palLen = 0;
	while (center < seqLen){
		if (center > palLen && seq[center - palLen - 1] == seq[center]){
			palLen += 2;
			center += 1;
			continue;
		}
		if (palLen > longestPal.length){
			longestPal = seq.substr(center - palLen,palLen);
		}
		l.push(palLen);
		var s = l.length - 2;
		var e = s - palLen;
		if (s==e) {
			broke();
			continue;
		}
		for (var j = s; j >= e; j--) {
			d = j - e - 1;
			if (d<0 || j<0) break;
			if (l[j] == d){
				palLen = d;
				break;
			}
			l.push(Math.min(d,l[j]));
		}
		function broke(){
			palLen = 1;
			center += 1;
		}
	}
	l.push(palLen);
	lLen = l.length;
	st = lLen - 2;
	en = st - (2 * seqLen + 1 - lLen);
	for (var k = st; k >= en; k--) {
		if (k<0) break;
		d = k - en - 1;
		var uh = l[k] || false;
		l.push(Math.min(d, uh));
	};
	return longestPal;
}