Once i was asked to write an algorithm which matches the two strings and tell the difference between them.
In other words we have two sentences
1. Its raining cats and dogs since morning
2. Its raining monkey and dogs since morning.
than the algorithm should efficient enough to detect the difference between the two strings.
In the above example it should tell that there are two difference in the string.
i-e monkeys found at the place of cat.
In order to implement the algorithm i would recommend to use
Diff takes two texts and finds the differences. This implementation works on a character by character basis. The result of any diff may contain 'chaff', irrelevant small commonalities which complicate the output. A post-diff cleanup algorithm factors out these trivial commonalities.
Google Difference Match patch
You can find it here
The Diff Match and Patch libraries offer robust algorithms to perform the operations required for synchronizing plain text.
- Compare two blocks of plain text and efficiently return a list of differences.
- Diff Demo
- Given a search string, find its best fuzzy match in a block of plain text. Weighted for both accuracy and location.
- Match Demo
- Apply a list of patches onto plain text. Use best-effort to apply patch even when the underlying text doesn't match.
- Patch Demo
Vajahat Ali Niazi