Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

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
3  
    
This is probably what you are looking for: en.wikipedia.org/wiki/Longest_common_subsequence_problem –  mrpyo Apr 29 '13 at 8:55
add comment

2 Answers

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
add comment

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

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

Your Answer

 
discard

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.