Checking two strings against eachother for errors

[ZippyDee]

Hi, I'm making a typing game that focuses on developing typing speed and accuracy. In part of this game, the user has to type a given word in a certain amount of time. If the user types the whole word within the time limit, the timer stops and it results in 100% accuracy for that word. However, if the user does not type the word within the time limit, I want to compare the typed word to the given word and find out how many errors they made.

I found this to be a lot more complicated that I had expected it to be. Fore example, if a letter was accidentally skipped or an extra letter was added, it will make all following characters seem wrong, even though the user only made one mistake.

How do I go about comparing the two strings?

Thanks!
-Zippy Dee
Ted Newman

[windmilltilter]

Yes, its a rather non-trivial problem. Here's an algorithm with code that illustrates a kind of approach:

http://en.wikipedia.org/wiki/Boyer%E...arch_algorithm

[ZippyDee]

Okay, so that finds the position of a string inside a larger string, but what I need to do is compare two strings (the prompt word & the typed word) and find out how much the typed word differs from the prompt word.

By the end of this calculation I need to have a value representing the typist's accuracy as a percent.

[ZippyDee]

Here is the algorithm I've come up with. It works pretty well, but I wrote it from scratch. I'm just wondering if there is a better method out there to use.

//  w1 = The prompt string
//  w2 = The typed string
//
function checkAccuracy(w1,w2):Number{
	var i=0; //pointer for w1
	var j=0; //pointer for w2
	var err=0; //number of errors found
	var offset=w2.length-w1.length; //the difference in length of w1 & w2.
				//Determines how many extra/missed characters to take into account (from the current position in the string) when processing.
	while(i<w1.length && j<w2.length){
		var c1=w1.substr(i,1); //character in w1 at i
		var c2=w2.substr(j,1); //character in w2 at j
		if(c1==c2){
			//if the two characters match
			//advance both string pointers
			i++;
			j++;
		}else if(w1.indexOf(c2,i)==-1){
			//if c2 is not found past index i of w1
			if(offset>0){
				//if the typed string had any extra characters
				j++; //advance typed string pointer
				err++; //add to error count
				offset--; //decrease extra character count
			}else{
				//otherwise, the current character is a wrong letter
				i++; //advance string pointers
				j++;
				err++; //add to error count
			}
		}else if(offset>=0){
		//if c2 IS in w1...
			//if there are at least 0 extra characters
			j++; //advance w2 pointer
			err++; //add to error count
			offset--; //decrease extra character count
		}else if(offset<0){
			//otherwise, if there were any missing characters
			i++; //advance to the next character in w1
			err++; //add to error count
			offset++; //decrease missing character count (increase the offset toward 0)
		}
	}
	//return the number of errors found
	return err;
}