Text comparison algorithm

The specific algorithm used by diff and most other comparison utilities is Eugene Myer's An O(ND) Difference Algorithm and Its Variations. There's a Java implementation of it available in the java-diff-utils package.

Some kind of diff variant might be helpful, eg wdiff

If you decide to devise your own algorithm, you're going to have to address the situation where a sentence has been inserted. For example for the following two documents:

The men are bad. I hate the men

and

The men are bad. John likes the men. I hate the men

Your tool should be able to look ahead to recognise that in the second, I hate the men has not been replaced by John likes the men but instead is untouched, and a new sentence inserted before it. i.e. it should report the insertion of a sentence, not the changing of four words followed by a new sentence.

Typically this is accomplished by finding the Longest Common Subsequence (commonly called the LCS problem). This is how tools like diff work. Of course, diff is a line-oriented tool, and it sounds like your needs are somewhat different. However, I'm assuming that you've already constructed some way to compare words and sentences.

An O(NP) Sequence Comparison Algorithm is used by subversion's diff engine.

For your information, there are implementations with various programming languages by myself in following page of github.

https://github.com/cubicdaiya/onp