# 解题思路 尽管所有WA,但和别人代码结果一致
# 找最小重叠部分(minOverlap,mo)
# dfs从龙头开始深度遍历,能找到重叠部分(mo),递归遍历;找不到,更新当前龙的最大值
def is_mo(word1, word2): # word1和word2是否有最小重叠部分,返回重叠下标
len1 = len(word1)
len2 = len(word2)
num = min(len1, len2) - 1 # num为比较最小重叠部分的最多次数,-1不能存在包含关系
for k in range(1, num + 1):
for i in range(len1 - 1, -1, -1):
for j in range(len2):
if word1[len1 - k:] == word2[:k]: # 比较是否有最小重叠部分
# global ind1,ind2 全局变量回溯的时候,删除的单词是等长的,ind2被覆盖了
# ind1=len1-k
ind2 = k
return ind2 # 重叠时word1,word2的下标
return -1
def dfs(): # 搜索龙头和其他(包括自己)单词有最小重叠部分
for j in range(n):
if use[j] <= 1:
global dragon
if is_mo(dragon, words[j]) != -1:
temp_str = words[j]
index2 = is_mo(dragon, words[j])
dragon += temp_str[index2:] # 接龙
use[j] += 1 # words[j]使用次数+1
dfs() # 搜索第j个单词是否还有龙
use[j] -= 1 # 回溯去标号
dragon = dragon.rstrip(temp_str[index2:]) # 回溯
# 深度遍历到了最深一层,单词都用完,此时龙最大
global max_len
if len(dragon) > max_len:
max_len = len(dragon)
return True
n = int(input())
words = [] # 存储所有单词
dragon = ''
use = [0] * (n) # 记录所有单词使用次数
max_len = 0 # 龙最大值
for _ in range(n):
str1 = input()
words.append(str1)
head = input()
for word in words:
if head == word[0]:
ind = words.index(word)
use[ind] += 1
dragon += word
dfs()
dragon = ''
print(max_len)