Created
May 15, 2013 13:38
-
-
Save JulianDuniec/5584065 to your computer and use it in GitHub Desktop.
Palindromes
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| <!DOCTYPE html> | |
| <html> | |
| <head> | |
| <script type="text/javascript" src="palindromes.js"></script> | |
| <script type="text/javascript"> | |
| function findPalindromesInInput() { | |
| var inputString = document.getElementById('input').value; | |
| var inputStream = new InputStream(inputString); | |
| var palindromeFinder = new PalindromeFinder(inputStream); | |
| document.getElementById('results').innerHTML = palindromeFinder.getPalindromes().join('<br />'); | |
| } | |
| </script> | |
| </head> | |
| <body> | |
| <input type="text" id="input" value="sabbasosabiiooiixyxyxyuwnaweoiwoowoowooijkjnasdiunmdnnsnasjnjuuwuuwnhd" style="width:500px" /> | |
| <input type="submit" onclick="findPalindromesInInput()" value="find palindromes" /> | |
| <hr /> | |
| <div id="results"></div> | |
| </body> | |
| </html> |
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| /* | |
| "Mock" text stream that has one method to | |
| read read the next character | |
| */ | |
| var InputStream = function(s) { | |
| var s = s.split('').reverse(); | |
| return { | |
| next : function(){ | |
| if(s.length == 0) | |
| return null; | |
| return s.pop(); | |
| } | |
| }; | |
| } | |
| var PalindromeFinder = function(input) { | |
| /* | |
| Helper method to extract a slice | |
| of a character array as a string | |
| */ | |
| function getString(buffer, from, to){ | |
| var s = ""; | |
| for(var i = from; i < to; i++) { | |
| s += buffer[i]; | |
| } | |
| return s; | |
| } | |
| return { | |
| getPalindromes : function() { | |
| var res = []; | |
| var currentChar = null; | |
| var buffer = []; | |
| var i = 0; | |
| var currentCenter = null; | |
| while( | |
| (i < buffer.length && buffer.length > 0) | |
| || (currentChar = input.next()) != null) { | |
| if(currentChar != null) | |
| buffer.push(currentChar); | |
| if(buffer.length > 1) { | |
| if(currentCenter == null) { | |
| //Search for a possible center by comparing to the previous char (ex: bb) | |
| //or one back (ex. sos). | |
| if(buffer[i] == buffer[i-1]) | |
| currentCenter = i-1; | |
| else if(buffer[i] == buffer[i-2]) | |
| currentCenter = i-2; | |
| } else { | |
| --currentCenter; | |
| if( | |
| //We are in a center | |
| (currentCenter != null) && | |
| //And the next character is not a part of a palindrome | |
| (buffer[i] != buffer[currentCenter]) | |
| //or we haven't got any more characters from the | |
| //stream | |
| || currentChar == null) { | |
| //Append the current found palindrome | |
| res.push(getString(buffer, currentCenter+1, i)); | |
| //reset the center | |
| currentCenter = null; | |
| } | |
| } | |
| } | |
| ++i; | |
| } | |
| return res; | |
| }, | |
| } | |
| } | |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment