shunfurh
编程介的小学生
采纳率92.7%
2017-05-27 12:12 阅读 981
已采纳

Find the Shortest Common Superstring

Problem Description
The shortest common superstring of 2 strings S1 and S2 is a string S with the minimum number of characters which contains both S1 and S2 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.

Input
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 S1 and the second line contains the string S2. Both of these strings contain at least 1 and at most 1.000.000 characters.

Output
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.

Sample Input
2
alba
bacau
resita
mures

Sample Output
7
8

  • 点赞
  • 写回答
  • 关注问题
  • 收藏
  • 复制链接分享

1条回答 默认 最新

相关推荐