Find the Shortest Common Superstring

The shortest common superstring of 2 strings S₁ and S₂ is a string S with the minimum number of characters which contains both S₁ and S₂ as a sequence of consecutive characters. For instance, the shortest common superstring of “alba” and “bacau” is “albacau”.
Given two strings composed of lowercase English characters, find the length of their shortest common superstring.

The first line of input contains an integer number T, representing the number of test cases to follow. Each test case consists of 2 lines. The first of these lines contains the string S₁ and the second line contains the string S₂. Both of these strings contain at least 1 and at most 1.000.000 characters.

For each of the T test cases, in the order given in the input, print one line containing the length of the shortest common superstring.

2
alba
bacau
resita
mures

7
8

Mugurel Ionut Andreica

Politehnica University of Bucharest Local Team Contest 2007