Palindrom Detection


Palindrom detection might be a simple task but I suggest this (yes, a bit complicated) solution:

  1. build clusters from the string
  2. pick a cluster from the clusters array as long as there are “unvisited” clusters. Return prematurely when there is already historized result longer then 1/2 of the whole string
  3. traverse the cluster and check if the current character is a palindrom
  4. enlarge the palindrom until the leading and trailing characters of the “possible” palindrom are equal
  5. store found palindrom inside of the cluster
  6. detect the maximum value and return it

There are two involved javascript classes:

  • Cluster is encapsulating the data
  • PalindromDetector builds the clusters and returns the max. value

The test method brings them together…

See it in action here: http://softwarechaos.byethost22.com/palindrom/palindrom.html

Note: the algorithm was extended by visualization of single steps by jQuery queue mechanism.

Code:

/*
Palindrom algorithm
golbang 2012
 */

function Observable() {
	this.observers = [];
}

Observable.prototype.addObserver = function(observer) {
	this.observers.push(observer);
};

Observable.prototype.addObservers = function(observers) {
	for( var i=0; i<observers.length;i++ ) {
		this.addObserver(observers[i]);
	}
};

Observable.prototype.notify = function( action, params ) {
	for( var i=0; i<this.observers.length; i++ ) {
		this.observers[i].update( action, params );
	}
};

Observable.prototype.removeAll = function() {
	if( this.observers == null )
		return;
	while( this.observers.length > 0 ) {
		this.observers.pop();
	}
	this.observers = null;
};

function Cluster(index,data) {
	this.index = index;
	this.data = data;

	this.cache = data;

	this.visited = false;

	this.prevIndex = -1;
	this.nextIndex = -1;

	this.left = -1;
	this.right = -1;

	this.history = [];

	$.extend( this, new Observable() );
};

Cluster.prototype.init = function() {
	this.prevIndex = (this.index > 0) ? this.index-1 : -1;
	this.nextIndex = (this.index < (Cluster.ALL.length-1)) ? this.index+1 : -1;	

	this.notify( "cluster-created", [this.index, this.data] );
};

Cluster.prototype.isPalindrom = function( index ) {
	var left = null;
	var right = null;
	if( index <= 0 ) {
		if( this.prevIndex != -1 ) {
			var prev = Cluster.ALL[this.prevIndex];
			left = prev.cache.charAt( prev.cache.length-1);
		}
	} else {
		left = this.cache.charAt(index-1);
	}

	if( index >= this.cache.length-1) {
		if( this.nextIndex != -1 ) {
			var next = Cluster.ALL[this.nextIndex];
			right = next.cache.charAt(0);
		}
	} else {
		right = this.cache.charAt(index+1);
	}
	return ( left == right );
};

Cluster.prototype.grab = function() {
	var i=0;
	while( i<this.cache.length) {
		if( this.isPalindrom(i) ) {
			this.expand(i);
			var right = this.history[this.history.length-1].right;
			i = right;
		}
		i++;
	}
	this.visited = true;
};

Cluster.prototype.historize = function() {
	if( this.left == -1 || this.right == -1 )
		return;
	this.history.push( {"left" : this.left, "right" : this.right} );

	this.notify( "result-historized", [ this.index, this.cache, this.left, this.right ] );

	this.left = -1; this.right = -1;
};

Cluster.prototype.getBestResult = function() {
	if( this.history.length == 0 )
		return null;
	var itm = null;
	for(var i=0; i<this.history.length; i++) {
		var _itm = this.history[i];
		if( i == 0 ) {
			itm = _itm;
			continue;
		}
		if( ( _itm.right-_itm.left ) > ( itm.right - itm.left ) )
			itm = _itm;
	}
	return itm;
};

Cluster.prototype.getBestResultAsString = function() {
	var best = this.getBestResult();
	if( best == null )
		return "";
	return this.cache.substring( best.left, best.right+1 );
};

/**
 * 
 * @returns {Number} offset to be considered
 */
Cluster.prototype.enlargeLeft = function() {
	if( this.prevIndex == -1 )
		return 0;

	var prev = Cluster.ALL[this.prevIndex];

	var offset = prev.data.length;

	this.cache = prev.data + this.cache;
	this.notify( "cluster-enlarged", [ this.index, this.cache ] );

	this.left = offset + this.left;
	this.right = offset + this.right;

	for( var i=0; i<this.history.length; i++ ) {
		this.history[i].left += offset;
		this.history[i].right += offset;
	}

	if( this.prevIndex > 0 )
		this.prevIndex = this.prevIndex-1;
	else
		this.prevIndex = -1;

	return offset;
};

Cluster.prototype.enlargeRight = function() {
	if( this.nextIndex == -1 )
		return 0;

	var next = Cluster.ALL[this.nextIndex];

	var offset = next.data.length;
	this.cache = this.cache + next.data;
	this.notify( "cluster-enlarged", [ this.index, this.cache ] );

	if( this.nextIndex < Cluster.ALL.length-1 )
		this.nextIndex = this.nextIndex+1;
	else
		this.nextIndex = -1;

	return offset;
};

Cluster.prototype.expand = function(index) {	
	var j = 1;
	while( true ) {
		var leftI = index-j;
		var rightI = index+j;

		if( leftI == -1 ) {
			var offsetLeft = this.enlargeLeft();
			if( offsetLeft == 0 ) {
				this.historize();
				break;
			}
			leftI += offsetLeft;
			rightI += offsetLeft;
			index += offsetLeft;
		}
		if( rightI == this.cache.length ) {
			var offsetRight = this.enlargeRight();
			if( offsetRight == 0 ) {
				this.historize();
				break;
			}
		}

		var left = this.cache.charAt(leftI);
		var right = this.cache.charAt(rightI); 
		if( left != right ) {
			this.historize();
			break;
		}

		this.left = leftI;
		this.right = rightI;
		j++;
	}
};

function PalindromDetector() {
	this.clusters = [];
	$.extend( this, new Observable() );	
};

PalindromDetector.prototype.pickCluster = function() {
	var restIndexes = [];
	for( var i=0; i<this.clusters.length; i++ ) {
		var c = this.clusters[i];
		if( !c.visited ) {
			restIndexes.push( i );
		}
	}
	if( restIndexes.length == 0 )
		return null;

	var j = -1;
	if( restIndexes.length == 1 )
		j = 0;
	else
		j = Math.floor( Math.random() * restIndexes.length );
	if( j == -1 )
		return null;
	return this.clusters[ restIndexes[ j ] ];
}; 

PalindromDetector.prototype.buildClusters = function( str, size ) {
	Cluster.ALL = null;
	this.clusters = [];

	var pieces =  Math.ceil(str.length/size);
	for( var i=0; i<pieces; i++ ) {
		this.clusters[i] = new Cluster( i, str.substr(i*size, size) );
	}
	Cluster.ALL = this.clusters;

	for( var i=0; i<this.clusters.length; i++ ) {
		var c = this.clusters[i];
		c.addObservers( this.observers );
		c.init();
	}	
};

PalindromDetector.prototype.getMaxCluster = function() {
	var maxC = null;
	for( var i=0; i<this.clusters.length; i++ ) {
		var c = this.clusters[i];

		if( !c.visited ) 
			continue;
		if( c.history.length == 0 )
			continue;

		if( maxC == null ) {
			maxC = c;
			continue;
		}
		var cResult = c.getBestResult();
		var maxcResult = maxC.getBestResult();
		if( cResult && maxcResult ) {
			var cResultLength = cResult.right - cResult.left;
			var maxcResultLength = maxcResult.right - maxcResult.left;
			if( cResultLength > maxcResultLength )
				maxC = c;
		}
	}
	return maxC;
};

PalindromDetector.prototype.hasUnvisitedClusters = function() {
	for( var i=0; i<this.clusters.length; i++ ) {
		var c = this.clusters[i];
		if( !c.visited )
			return true;
	}
	return false;
};

PalindromDetector.prototype.destroy = function() {
	for( var i=0; i<this.clusters.length; i++ ) {
		this.clusters.pop();
	}
	this.clusters = null;
	Cluster.ALL = null;
};

PalindromDetector.prototype.detect = function( str ) {
	try {
		if( str.length == 0 ) {
			this.notify("show-error", [ "Insert valid string!" ] );
			return;
		}
		str = str.toLowerCase().replace( /[^a-zA-Z0-9]/gi, '' );

		this.notify( "hide-error", [] );

		var size = Math.floor( str.length / 10 ); //divide them to 10 clusters
		if( size < 3 ) size = 3;

		this.notify( "start", [] );

		this.buildClusters( str, size );
		Cluster.ALL = this.clusters;			
		do {

			var c = this.pickCluster();
			if( c == null )
				break;

			this.notify( "cluster-picked", [ c.index ] );
			c.grab();

			var bestResult = c.getBestResult();
			if( bestResult && ( bestResult.right-bestResult.left+1 > Math.floor( str.length/2 ) ) ) {
				break;
			}

		} while( this.hasUnvisitedClusters() );

		var maxCluster = this.getMaxCluster();
		if( maxCluster == null ) {
			this.notify("show-error", ["There is no palindrom."] );
			return;
		}

		var result = maxCluster.getBestResult();
		this.notify( "finish", [ maxCluster.index, maxCluster.cache, result.left, result.right ] );	
	} finally {
		this.destroy();
	}
};
function test() {
    var detector = new PalindromDetector();        
    detector.detect("aieutakgjhkdfhjatasosataeirejhke");
    var max = detector.getMaxCluster();
    var best = max.getBestResultAsString();
    alert( best );
};
Advertisements

3 thoughts on “Palindrom Detection

  1. def palindrome?(analysed_string)
    if analysed_string.to_s == analysed_string.reverse.to_s
    true
    else
    false
    end
    end

    def find_longest_palindrome(text)
    longest_palindrome = “”
    (0..text.size – 1).each do |test_index|
    (test_index..text.size-test_index).each do |test_length|
    test_length -= 1 if test_length > 0
    string_tested = text[test_index..test_length]
    longest_palindrome = string_tested if palindrome?(string_tested) && string_tested.length > longest_palindrome.length
    end
    end
    puts longest_palindrome
    end

    palindrome_test = “dsfasmhrfbwedofyu8a4wflaflasrkhaserf,laewabzbafjhasfaslkfjasdhfrtyuiuytrsdalfskdhfbnm,mnbzxcvbnbvcxzjskdhfaserlakujasdfasi”
    find_longest_palindrome(palindrome_test)

  2. Pingback: Palindrom Detection II « softwarechaos

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s