Programmer's Notebook

A Longest Common Substring Function for Javascript

Here is a down and dirty Javascript function that returns the longest substring shared by two string variables. In other words, given the two sentences:

"I'm looking for a little string within a big string." and
"Why here's a little string now!",:

The function will return the string " a little string".

The function, named lcs, will return a string as small as a single character. "123" and "345" will return "3". If no match is found, lcs returns a null string.

The lcs function:

Usage is fairly straightforward. Include the function as supplied. Since lcs returns a value, you will need to assign it to a variable. The function takes two values - one for each string. Although lcs will find the longest match regardless of the order presented, your code will execute more efficiently if it is possible to list the shorter string first.

A sample usage would be:

The function makes use of Javascript's Regular Expressions engine and two nested loops to provide a very simple solution to the common string problem. It begins by searching for the first string within the second string in its entirety. Failing to find the full string, the function then reduces the length of the test string by one and tests all possible substrings of that length. So if the full string were "1234", on the second iteration the function would search for "123" and "234". Every time the function fails it reduces the length of the test string and tries again. So the third iteration would test for "12", "23", and "34". Once the function finds a match, it sets the return value to that match and breaks out of the loop. If a match is never found, the result is set to an empty string to avoid generating errors further down the line.

There are numerous approaches to this problem that would likely result in faster, more efficient coding. In fact, the longest common substring problem is the subject of quite a bit of research and discussion. The main virtues of this function are that it is written in Javascript and that it is easy to understand.

See more from Web Design


Other Pages You Might Enjoy...

The Meissen Porcelain Manufactory
For more than 300 years the Meissen Porcelain Manufactory has been a central figure in European porcelain. It was at Meissen that the first true hard-paste porcelain was manufactured outside of China, and the story of that accomplishment has the high drama of fiction - all the more intriguing because it is true.

Pirated Glassware that Collectors Want to Own
The 1996 discovery of what is believed to be the wreckage of Blackbeardís ship Queen Anneís Revenge, is providing historians and collectors new information about the fragile and transparent objects that came onto the North American Continent before arrival of the first piece of cut glass.

Collecting Antique Furniture
Of all the collectible antiques, the broad category of furniture is perhaps the most widely held and most satisfying. Frequently handed down through generations, the various chairs, tables, cabinets and other pieces are often in use, adding character and constancy to our daily lives. This guide includes an overview of the significant styles and historical periods, and other important information for collectors.

Collecting Antique Clocks and Watches
Information for collectors of antique clocks and watches. Includes a history of clock and watchmaking, an overview of styles, and important terminology.

Collecting Antique Jewelry
Embodying the wealth and treasure of bygone days, the antique jewelry pieces available today include some of the world's most valuable artifacts. Includes a history of jewelry making, an overview of the major historical periods, and a glossary of antique jewelry terminology.

Javascript Chatterbot Workshop
Home of the Do It Yourself Chatterbot Project. Has a ready to go chatterbot shell and full instructions on how to program it.

An Unorthodox Javascript Form Submission
Describes three fixes in handling an unorthodox Javascript form submission. Executing Javascript before submitting the data to the server; altering the behavior of the PHP running on the server so that it would return to the original page; and restarting animated GIFs.

Bring Your Web Site to Life With PHP
PHP is the scripting language that powers some of the biggest Web 2.0 content providers in the business. Whether you're looking to add a simple feedback form to your site, or have your heart set on building the next Facebook, read up on PHP in this informative tutorial and get started tonight.

Use JavaScript to Dynamically Update Your Website
Learn to use this simple JavaScript technique to change content and make instant updates across your entire site. Whether you update five pages or thousands, this handy web tip is a must read!

Using HTML Tables to Format Your Web Page
Follow these simple steps to master the use of the HTML table features and deliver beautiful layouts for all of your web page design work.

Tips for Improving Website Navigation
In order for visitors to find the right information, a website's navigation path needs to be clear. Without a clear navigation path, visitors will become confused and leave before they can make a purchase.In order for visitors to find the right information, a website's navigation path needs to be clear. Without a clear navigation path, visitors will become confused and leave before they can make a purchase.

Choosing the Right Color for Your Web Site
When people build a web site for their business (or hire a web design company to make it for them), not much thought is put into deciding what color their web site will be as most would rather focus on more important tasks like creating content, web site optimization and promotion. Most simply choose the most web-friendly colors, others use their companyís logo as base while some decide to just use their favorite color.

Designing A Website That Loads Quickly
The amount of time it takes for your website to load onto the visitor's screen is a major influence on traffic to your site. Research has shown that most internet users will leave your website if it takes more than 10 seconds to load and some potential guests will exit even faster. A quick loading website is vitally important to the success of your site.

How to Create Web2.0 Applications using AJAX and Clientside HTTP Requests
AJAX is an acronym that stands for Asynchronous Javascript and XML. A web 2.0 application, or AJAX application, runs on a single web page, and uses clientside javascript to initiate and process additional requests to the server.

Getting a Grip on VBScript Arrays with UBound
The ubound function returns the highest subscript in the given dimension of an array and can simplify your array handling tasks.

VBScript Split Function
The VBScript Split function takes a string and returns an array broken up by the delimiter of your choosing. This functionality can make short work of parsing plain text, CSV, tab delimitted, or virtually any type of string you can imagine.


The MiFio Network

Visit cache.MiFio.com for more pages about business, technology, programming, home, travel and more.

Visit www.MiFio.com the website dedicated to antiques and collectibles.