Match Differences Between Two Strings

Hi friends,

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
It is an open source algorithm written in the Java, JavaScript, C++, C#, Lua and Python.
You can find it here
http://code.google.com/p/google-diff-match-patch/

The Diff Match and Patch libraries offer robust algorithms to perform the operations required for synchronizing plain text.

1. Diff:
• Compare two blocks of plain text and efficiently return a list of differences.
• Diff Demo
2. Match:
• Given a search string, find its best fuzzy match in a block of plain text. Weighted for both accuracy and location.
• Match Demo
3. Patch:
• Apply a list of patches onto plain text. Use best-effort to apply patch even when the underlying text doesn't match.
• Patch Demo

Currently available in Java, JavaScript, C++, C#, Lua and Python. Regardless of language, each library features the same API and the same functionality. All versions also have comprehensive test harnesses.

Thanks
Vajahat Ali Niazi
Lahore Pakistan