## 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:

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

## 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 *'));