传送门= ̄ω ̄=

思路:建立有向图!对于输入的字符串s[i]和s[j],dis[i][j]表示字符串s[j]接在s[i]后面时的重叠部分的长度。用函数con(i,j)计算dis[i][j]的值(注意!dis[i][j]不一定等于dis[j][i]!)。在函数con中,我采用了STL的双端队列(deque),它可以从容器首位插入元素,并且支持==比较运算。然后再用dfs找最长路,把字符串s[i]和s[j]接起来产生的长度为s[i]的长度+s[j]的长度-dis[i][j]。

特别注意!一开始我就被这个坑了!每个单词可以用2次!

代码:

至于vjudge上的HRBUST - 1213,有多组数据。。。
所以一开始我蜜汁WA。。。
代码: