努力学习第八天

单词接龙

给定n个单词，和一个开头字母st，每个单词可以使用两次

要求找到以st开头的单词接上能与之相接的单词的最长长度

规则：两个单词之间有重叠部分才能够相接，但是如果两个单词之间是包含关系则两个单词不能相接

解题思路：

（1）输入完毕后，对于每两个单词之间，预处理出它们的重叠部分（注意：两个单词互换位置后的重叠部分与互换之前是不一样的）

（2）接下来，让我们来研究一下这个预处理（大家可以用草稿本模拟一下）：

①我们用lap[i][j]来表示单词i和单词j之间的重叠长度（注意顺序）

②我们用overlap函数来处理两个单词之间的重叠部分

③在overlap函数中，用lenx和leny分别存储单词x和单词y的长度，然后双重循环处理

④第一层循环i从lenx~1到0（即倒序搜寻单词x），当word[x][i]等于单词y的第一个字母时，进入第二层循环

⑤设置k=i，第二层循环j从0~leny（正序遍历单词y），当word[x][k]==word[y][j]时，k++；否则跳出第二层循环

⑥每一次跳出第二层循环后，判断k是否等于lenx，如果是就直接返回k-i（lenx-i）；不相等就继续循环

⑦如果第一层循环完之后，k都始终不等于lenx，则说明两个单词没有重叠部分，返回0

（3）烧脑的预处理结束后，就简单了，直接循环单词列表，如果当前单词的首字母等于开头字母st，就进入DFS找出以当前单词能连成的最大长度sum，每找完一次（用pd来标记）就用ans选出最大值，最后输出ans即可

（4）DFS部分和模板差不多，只是需要注意判断一下当前单词是否已经用过两次，是的话就直接不考虑这个单词（用一个ti数组来存储次数即可）；而且要注意回溯完整：sum、ti都需要回溯