Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I have the following task: developing a program where there is a block of sample text which should be typed by user. Any typos the user does during the test are registered. Basically, I can compare each typed char with the sample char based on caret index position of the input, but there is one significant flaw in such a "naive" approach. If the user typed mistakenly more letters than a whole string has, or inserted more white spaces between the string than should be, then the rest of the comparisons will be wrong because of the index offsets added by the additional wrong insertions.

I have thought of designing some kind of parser where each string (or even a char ) is tokenized and the comparisons are made "char-wise" and not "index-wise," but that seems to me like an overkill for such a task. I would like to get a reference to possibly existing algorithms which can be helpful in solving this kind of problem.

share|improve this question
This is probably what you are looking for: – mrpyo Apr 29 '13 at 8:55

It sounds like what you need is equivalent to doing a 'diff' on two files. There are many ways to do this, but I'd look into Google's diff-match-patch algorithm.

share|improve this answer

Pretty much the only way to do this is to use grapheme clusters and then compare their normalized versions.

share|improve this answer
Could you extend on this a little bit? – Michael IV Mar 2 '13 at 17:51

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.