Solving the longest common substring problem with AS3

The longest common substring problem is to find the longest string (or strings) that is a substring (or are substrings) of two strings.

This means if we have two strings, let’s say “ampersand” and “misunderstanding”, the result is given by “ers” and “and”. It may seem a silly exercise but it’s the basic of most text revision software.

Let’s see how to solve it: just like for the Levenshtein distance, we need a matrix where to place both strings.

We’ll make the example with “sick” and “bricks”. Look at the picture:

From left, to right, we fill the matrix with zeros, then from row to row starting from the upper to the lower we scan all characters from left to right looking for matches. If letters match, the corresponding value will take 1+the value of its upper left cell. At the end we’ll select the element with the higher number, and in going backward in the diagonal we’ll find the longest common substring. If more cells have the same value, there will be more than one solution to the problem. In this case is “ick”

Let’s see it running with AS3:

package {
	import flash.display.Sprite;
	import flash.text.TextField;
	import flash.text.TextFieldType;
	import flash.text.TextFormat;
	import flash.events.Event;
	public class longest extends Sprite {
		private var from:TextField=new TextField();
		private var to:TextField=new TextField();
		private var lcs:TextField=new TextField();
		private var text_format:TextFormat = new TextFormat();
		public function longest() {
			text_format.color=0x000000;
			text_format.size=24;
			addChild(from);
			with (from) {
				type=TextFieldType.INPUT;
				x=20;
				y=20;
				width=460;
				height=30;
				text="string";
				border=true;
				setTextFormat(text_format);
				addEventListener(Event.CHANGE,on_change);
			}
			addChild(to);
			with (to) {
				type=TextFieldType.INPUT;
				x=20;
				y=70;
				width=460;
				height=30;
				text="substring";
				border=true;
				setTextFormat(text_format);
				addEventListener(Event.CHANGE,on_change);
			}
			addChild(lcs);
			with (lcs) {
				x=20;
				y=120;
				width=460;
				height=30;
				text="LCS = "+strlcs(from.text,to.text);
				setTextFormat(text_format);
			}
		}
		private function strlcs(from:String,to:String):String {
			// finding lengths of both strings
			var from_len:uint=from.length;
			var to_len:uint=to.length;
			// longest is the array which will contain the longest string(s)
			var longest:Array=new Array();
			// lcs is the matrix used to determine the longest string(s)
			var lcs:Array=new Array();
			// largest_til_now is the largest match found until now
			var largest_til_now:uint=0;
			// if one of the strings is empty, then we can't run the function
			if (from_len==0||to_len==0) {
				return "-";
			}
			// filling the matrix with zeros
			for (var i:uint=0; ilargest_til_now) {
							// update the largest match and empty the array
							largest_til_now=lcs[i][j];
							longest=new Array();
						}
						// if this element has the same value of the largest match...
						if (lcs[i][j]==largest_til_now) {
							// add it to matches array
							longest.push(from.substr(i-largest_til_now+1,largest_til_now));
						}
					}
				}
			}
			// return matches array
			return longest.toString();
		}
		public function on_change(e:Event):void {
			lcs.text="LCS = "+strlcs(from.text,to.text);
			lcs.setTextFormat(text_format);
		}
	}
}

The core of the script is strlcs function which is fully commented.

This is the result:

Change the strings in the text fields to see how the result updates.

Download the source code.

Get the most popular Phaser 3 book

Through 202 pages, 32 source code examples and an Android Studio project you will learn how to build cross platform HTML5 games and create a complete game along the way.

Get the book

214 GAME PROTOTYPES EXPLAINED WITH SOURCE CODE
// 1+2=3
// 100 rounds
// 10000000
// 2 Cars
// 2048
// A Blocky Christmas
// A Jumping Block
// A Life of Logic
// Angry Birds
// Angry Birds Space
// Artillery
// Astro-PANIC!
// Avoider
// Back to Square One
// Ball Game
// Ball vs Ball
// Ball: Revamped
// Balloon Invasion
// BallPusher
// Ballz
// Bar Balance
// Bejeweled
// Biggification
// Block it
// Blockage
// Bloons
// Boids
// Bombuzal
// Boom Dots
// Bouncing Ball
// Bouncing Ball 2
// Bouncy Light
// BoxHead
// Breakout
// Bricks
// Bubble Chaos
// Bubbles 2
// Card Game
// Castle Ramble
// Chronotron
// Circle Chain
// Circle Path
// Circle Race
// Circular endless runner
// Cirplosion
// CLOCKS - The Game
// Color Hit
// Color Jump
// ColorFill
// Columns
// Concentration
// Crossy Road
// Crush the Castle
// Cube Jump
// CubesOut
// Dash N Blast
// Dashy Panda
// Deflection
// Diamond Digger Saga
// Don't touch the spikes
// Dots
// Down The Mountain
// Drag and Match
// Draw Game
// Drop Wizard
// DROP'd
// Dudeski
// Dungeon Raid
// Educational Game
// Elasticity
// Endless Runner
// Erase Box
// Eskiv
// Farm Heroes Saga
// Filler
// Flappy Bird
// Fling
// Flipping Legend
// Floaty Light
// Fuse Ballz
// GearTaker
// Gem Sweeper
// Globe
// Goat Rider
// Gold Miner
// Grindstone
// GuessNext
// Helicopter
// Hero Emblems
// Hero Slide
// Hexagonal Tiles
// HookPod
// Hop Hop Hop Underwater
// Horizontal Endless Runner
// Hundreds
// Hungry Hero
// Hurry it's Christmas
// InkTd
// Iromeku
// Jet Set Willy
// Jigsaw Game
// Knife Hit
// Knightfall
// Legends of Runeterra
// Lep's World
// Line Rider
// Lumines
// Magick
// MagOrMin
// Mass Attack
// Math Game
// Maze
// Meeblings
// Memdot
// Metro Siberia Underground
// Mike Dangers
// Mikey Hooks
// Nano War
// Nodes
// o:anquan
// One Button Game
// One Tap RPG
// Ononmin
// Pacco
// Perfect Square!
// Perfectionism
// Phyballs
// Pixel Purge
// PixelField
// Planet Revenge
// Plants Vs Zombies
// Platform
// Platform game
// Plus+Plus
// Pocket Snap
// Poker
// Pool
// Pop the Lock
// Pop to Save
// Poux
// Pudi
// Pumpkin Story
// Puppet Bird
// Pyramids of Ra
// qomp
// Quick Switch
// Racing
// Radical
// Rebuild Chile
// Renju
// Rise Above
// Risky Road
// Roguelike
// Roly Poly
// Run Around
// Rush Hour
// SameGame
// SamePhysics
// Save the Totem
// Security
// Serious Scramblers
// Shrink it
// Sling
// Slingy
// Snowflakes
// Sokoban
// Space Checkers
// Space is Key
// Spellfall
// Spinny Gun
// Splitter
// Spring Ninja
// Sproing
// Stabilize!
// Stack
// Stick Hero
// String Avoider
// Stringy
// Sudoku
// Super Mario Bros
// Surfingers
// Survival Horror
// Talesworth Adventure
// Tetris
// The Impossible Line
// The Moops - Combos of Joy
// The Next Arrow
// Threes
// Tic Tac Toe
// Timberman
// Tiny Wings
// Tipsy Tower
// Toony
// Totem Destroyer
// Tower Defense
// Trick Shot
// Tunnelball
// Turn
// Turnellio
// TwinSpin
// vvvvvv
// Warp Shift
// Way of an Idea
// Whack a Creep
// Wheel of Fortune
// Where's my Water
// Wish Upon a Star
// Word Game
// Wordle
// Worms
// Yanga
// Yeah Bunny
// Zhed
// zNumbers