Intuidiff

Web applications compare the revision history of posts and articles with some variant of the classic diff utility, which finds a small set of insertions and deletions that turn one document into another.

Here is a typical problem with it. Suppose the original document is made up of two paragraphs, P1 P2, and we edit it to become P2 P1. Then diff might describe the changes as: delete P1, leave P2, insert some new text. The fact that the new text is equal to P1 is not used. So, in some sense, diff is linear and does not work in the most convenient way when we reorder parts of the document.

Can we do better? (More importantly, can it be finished today?) We adopt this basic requirement: when a part of the new version of a document has appeared somewhere in the old version, it should be highlighted to reflect this fact.

To capture that idea, define the Intuidiff distance from one document to another as the smallest integer $N$ such that the second document is the concatenation of $N$ blocks, where each block is either a substring of the first document or a single new character. Deletions do not matter here, because unlike diff we do not implicitly begin with the original document, we begin with an empty one. The Intuidiff distance from a document to itself is therefore 1, and that is the only counter-intuitive thing about it.

Given two strings, compute the Intuidiff distance from the first to the second.

The first line contains the first string. The second line contains the second string. Each string has length between 1 and 500 000 inclusive, and both strings consist only of alphanumeric characters and underscores.

Print the Intuidiff distance from the first string to the second string.

In the first example, one optimal split of the second string is p + aragraph_ + e + d + i + t + 3 + _ + Paragraph.