JavaScriptで差分アルゴリズムを実装

行番号とかの表示部分は未実装なのでダミーが入ってます。

```html
====== Wuのアルゴリズム ======

<html>
<head>
<title>Do</title>
<meta http-equiv="Content-Type" content="text/html; charset=UTF-8">

<style type="text/css">
<!--
.add{background-color:#B3EC96;}
.del{background-color:#F3A1A1;}
.in{width:40%;}
.out{display:inline-block;position:relative;left:-8px}
.outWrapper{width:85%;border:solid 1px #D5D5D5;}

.inIndex {display:inline-block;width:15px;border-right:solid 1px #D5D5D5;}
.outIndex{display:inline-block;width:15px;border-right:solid 1px #D5D5D5;position:relative;left:-4px}
.state   {display:inline-block;width:15px;position:relative;left:-8px}
.inIndex span,.outIndex span,.state span{margin:2px;}
//-->

</style>

</head>
<body>
<script language="JavaScript">
function doScript(valX,valY){

document.getElementsByClassName("out")[0].innerHTML=searchPath(valX,valY);
}
function searchPath(valX,valY){
	var maxLength=valX.length+valY.length;//編集回数の上限
	var path=[""];
	var posX=[0];
	var posY=[0];
	var map=Array(valX.length*valY.length);
	var p;
	for(var i=0;i<maxLength;i++){
		p=sSearch(valX,valY,posX,posY,path,map);
		if(p!=null)break;
	}
	return sdecode(valX,valY,path[p[0]]);
}

function sdecode(valX,valY,path){
	var res="";
	var pX=0;
	var pY=0;
	var pre="";
	for(var i=0;i<path.length;i++){
		if(path.charAt(i)=="e"){
			if(pre==""){pre="e";res+='<span>';}
			if(pre!="e"){pre="e";res+='</span><span>';}
			if(valX.charAt(pX)=="<")res+="&lt;";
			else if(valX.charAt(pX)==">")res+="&gt;";
			else res+=valX.charAt(pX);
			pX++;
			pY++;
		}else if(path.charAt(i)=="a"){
			if(pre==""){pre="a";res+='<span class="add">';}
			if(pre!="a"){pre="a";res+='</span><span class="add">';}
			if(valX.charAt(pX)=="<")res+="&lt;";
			else if(valX.charAt(pX)==">")res+="&gt;";
			else res+=valX.charAt(pX);
			pX++;
		}else if(path.charAt(i)=="d"){
			if(pre==""){pre="d";res+='<span class="del">';}
			if(pre!="d"){pre="d";res+='</span><span class="del">';}
			if(valY.charAt(pY)=="<")res+="&lt;";
			else if(valY.charAt(pY)==">")res+="&gt;";
			else res+=valY.charAt(pY);
			pY++;
		}
	}
	return res+='</span>';
}

function sSearch(valX,valY,posX,posY,path,map){
	var c=posX.length;//終端の個数
	var endPath=null;
	for(var i=0;i<c;i++){//各終端について
		while(posX[i]!=valX.length||posY[i]!=valY.length){//編集回数が1増える（追加か削除を行う）か、比較し終えるまで繰り返す
			if(valX.charAt(posX[i])==valY.charAt(posY[i])){
//				posX[posX.length]=posX[i]+1;//全列挙は無駄
//				posY[posY.length]=posY[i];
//				path[path.length]=path[i]+"a";
//				posX[posX.length]=posX[i];
//				posY[posY.length]=posY[i]+1;
//				path[path.length]=path[i]+"d";

				//同じ時は右下に進める
				if(map[(posX[i]+1)+(posY[i]+1)*(valX.length+1)]==true){
					//すでに通った経路がある場合には現在のノードを削除する
					posX.splice(i,1);
					posY.splice(i,1);
					path.splice(i,1);
					i--;
					c--;
					break;
				}else{
				map[(posX[i]+1)+(posY[i]+1)*(valX.length+1)]=true;
				posX[i]=posX[i]+1;
				posY[i]=posY[i]+1;
				path[i]=path[i]+"e";
				}
			}else{
				if(posX[i]==valX.length){
				//右端なら分岐せずに下に進める
					if(map[(posX[i])+(posY[i]+1)*(valX.length+1)]==true){
						//すでに通った経路がある場合には現在のノードを削除する
						posX.splice(i,1);
						posY.splice(i,1);
						path.splice(i,1);
						i--;
						c--;
					}else{
					map[(posX[i])+(posY[i]+1)*(valX.length+1)]=true;
					//posX[i]=posX[i];
					posY[i]=posY[i]+1;
					path[i]=path[i]+"d";
					i--;
					}
					
					break;
				}
				else if(posY[i]==valY.length){
				//下端なら分岐せずに右に進める
					if(map[(posX[i]+1)+(posY[i])*(valX.length+1)]==true){
						//すでに通った経路がある場合には現在のノードを削除する
						posX.splice(i,1);
						posY.splice(i,1);
						path.splice(i,1);
						i--;
						c--;
					}else{
					map[(posX[i]+1)+(posY[i])*(valX.length+1)]=true;
					posX[i]=posX[i]+1;
					posY[i]=posY[i];
					path[i]=path[i]+"a";
					}
					
					break;
				}
				else{
				//同じでない場合は分岐させる（新規を右に）(元を下へ進める)
					if(map[(posX[i]+1)+(posY[i])*(valX.length+1)]==true){
						//すでに通った経路がある場合には新しく作らない
						//posX.splice(i,1);
						//posY.splice(i,1);
						//path.splice(i,1);
					}else{
					map[(posX[i]+1)+(posY[i])*(valX.length+1)]=true;
					posX[posX.length]=posX[i]+1;
					posY[posY.length]=posY[i];
					path[path.length]=path[i]+"a";
					}
					
					if(map[(posX[i])+(posY[i]+1)*(valX.length+1)]==true){
						//すでに通った経路がある場合には現在のノードを削除する
						posX.splice(i,1);
						posY.splice(i,1);
						path.splice(i,1);
						i--;
						c--;
					}else{
					map[(posX[i])+(posY[i]+1)*(valX.length+1)]=true;
					//posX[i]=posX[i];
					posY[i]=posY[i]+1;
					path[i]=path[i]+"d";
					}
					
					break;
				}
			}
		}
		//もし右下まで着いた経路なら、記録しておく
		if(posX[i]==valX.length&&posY[i]==valY.length){
			if(endPath==null)endPath=[];
			endPath[endPath.length]=i;
		}
	}
	return endPath;
}

</script>
<form id="editor" action="/search" method="GET" onsubmit="doScript(this.valX.value,this.valY.value);return false;">
<textarea name="valY" class="in"> pre</textarea>
<textarea name="valX" class="in"> post</textarea>
<input type="submit" valXue="compare"/>
</form>
<div class="outWrapper">
<div class="inIndex"><span>1</span><br><br><span>2</span></div>
<div class="outIndex"><br><span>1</span><br><span>2</span></div>
<div class="state"><span>-</span><br><span>+</span><br><span></span></div>
<div class="out"><span class="del">dummy1</span><br><span class="add">dummy2</span><br><span>prev</span></div>
</div>
</body>
</html>
```