Month: May 2014
Find Longest Palindrome in a string
Find longest palindrome in a string.
Brute Force: N^3
Below Method by Dynamic Programming is N^2. Video for below method:
https://www.youtube.com/watch?v=obBdxeCx_Qs
There is another algorithm called Mancher’s Algorithm which is in linear time.
Note that here since we are dealing with single string we just need to populate top triangle of matrix. In longest substring since we were dealing with 2 strings we populated the whole matrix.
$str = "BANANA"; $len = strlen($str); $matrix = array(); $palindromeBegins = 0; $max = 1; // single letter palindromes for ($i=0; $i < $len; $i++) { $matrix[$i][$i] = 1; }; // 2 character palindromes for ($i=0; $i < $len-1; $i++) { if ($str[$i] == $str[$i+1]) { $matrix[$i][$i+1] = 1; $max = 2; $palindromeBegins = $i; } } // 3 character and above for ($curr_len=3; $curr_len <= $len ; $curr_len++) { for ($i=0; $i < $len-$curr_len+1; $i++) { $j = $i+$curr_len-1; // 1. first and last chars should match // 2. rest of string from previous calculations should be a palindrome if (($str[$i] == $str[$j]) && ($matrix[$i+1][$j-1] == 1)) { $matrix[$i][$j] = 1; $max = $curr_len; $palindromeBegins = $i; } } } echo "Max Palindome: $max\n"; echo "Palindrome: " . substr($str, $palindromeBegins, $max); echo "\n";
Another approach:
http://krenzel.org/articles/longest-palnidrome
ACID
In computer science, ACID (Atomicity, Consistency, Isolation, Durability) is a set of properties that guarantee that database transactions are processed reliably. In the context of databases, a single logical operation on the data is called a transaction.
Ajax and XMLHttpRequest
Ajax – an acronym for Asynchronous JavaScript and XML)[1] is a group of interrelated Web development techniques used on the client-side to create asynchronous Web applications. With Ajax, Web applications can send data to, and retrieve data from, a server asynchronously (in the background) without interfering with the display and behavior of the existing page. Data can be retrieved using the XMLHttpRequest object. Despite the name, the use of XML is not required; JSON is often used instead (see AJAJ), and the requests do not need to be asynchronous.
Technologies involved:
HTML (or XHTML) and CSS for presentation
The Document Object Model (DOM) for dynamic display of and interaction with data
XML for the interchange of data, and XSLT for its manipulation
The XMLHttpRequest object for asynchronous communication
JavaScript to bring these technologies together
XMLHttpRequest (XHR) is an API available to web browser scripting languages such as JavaScript. It is used to send HTTP or HTTPS requests to a web server and load the server response data back into the script. All browsers supports XMLHttpRequest.
typical use:
var xhttp = new XMLHttpRequest(); xhttp.onreadystatechange = function() { if (this.readyState == 4 && this.status == 200) { // Typical action to be performed when the document is ready: document.getElementById("demo").innerHTML = xhttp.responseText; } }; xhttp.open("GET", "filename", true); xhttp.send();
With Jquery :
$('#main-menu a').click(function(event) { event.preventDefault(); $.ajax(this.href, { success: function(data) { $('#main').html($(data).find('#main *')); $('#notification-bar').text('The page has been successfully loaded'); }, error: function() { $('#notification-bar').text('An error occurred'); } }); });