注意

  该博客是为了帮助同学学习，并非为了协助同学刷题，请读者保持自觉，请勿做CV工具人。另外为了节省篇幅，代码中不再写明#include及using，如果遇到我没有声明的函数或类，那么就是某一个头文件中的函数，读者搜索“std + 名字”就能查到相关信息。

题目

  单词接龙是一个与我们经常玩的成语接龙相类似的游戏，现在我们已知一组单词，且给定一个开头的字母，要求出以这个字母开头的最长的“龙”（每个单词都最多在“龙”中出现两次），在两个单词相连时，其重合部分合为一部分，例如 beast 和 astonish，如果接成一条龙则变为beastonish，另外相邻的两部分不能存在包含关系，例如at和atide间不能相连。

输入格式

  输入的第一行为一个单独的整数n（≤ 20）表示单词数，以下n行每行有一个单词，输入的最后一行为一个单个字符，表示“龙”开头的字母。你可以假定以此字母开头的“龙”一定存在。

输出格式

  只需输出以此字母开头的最长的“龙”的长度。

输入样例

5
at
touch
cheat
choose
tact
a

输出样例

23

题目解析

  可能很多人和我一样，第一眼看到题目一脸懵逼，完全不知道是什么东西，我们这里就分开详细解析一下这道题的题意。

重叠

  需要注意这里说的重叠是同向的而不是镜像的。

如何连接

  连接两个字符串的方式非常简单，比如：abcde + deabc = abcdeabc。

如何连接

最小重叠

  还有一点要注意，合并的是最小重叠区域，而不是最大重叠区域，比如：kmkm + kmkm = kmkmkm。

最小重叠

包含关系

  题目上说相邻两部分不能存在包含关系，那这个包含关系究竟指的是什么？像kmkm + kmkm是违反这个规定的吗？

  答案是不违反，因为题目的样例上就存在两个同样的字符串连接的情况（tact + tact = tactact）。

  这个包含关系其实指的是连接后字符串并没有变长的情况，比如：kmkm + km、acm + m。

能否连接

  我们可以知道两个字符串想要连接需要符合以下条件：

  1. 两个字符串连接后可以使得字符串变长
  2. 两个字符串必须有重叠的部分（比如：km + k是不允许的）
  3. 新连接的字符串使用次数不大于2

  这里需要注意这个坑，一个字符串可以使用0~2次。也就是说连接完成后一个字符串也可以一次都没用过。

思路解析

  我们首先需要有一个方法来判断两个字符串连接后可以使得整体变长多少，所以我们需要写一个simulate(string& pre, string& last)来计算。如果字符串不可连接就返回0.否则返回具体数值。

simulate

  simulate的编写就非常简单了，代码的原理就是先确定有多少个字符重叠，然后判断是否重叠，如果重叠则直接返回结果，否则一直判断到不可能出现重叠为止。

  上文提到的“包含关系”这里也处理到了。（其实对于这种写法也没有“包含关系”这一说了）。

1
2
3
4
5
6
7
8
9
10
11
12
int simulate(const string& pre, const string& last) {
    for (int length = 1; length != pre.length(); ++length) {
        if (length >= last.length()) return 0;
        int i = int(pre.length() - length);
        for (int k = 0; k != length; ++k) {
            if (pre[i + k] != last[k]) goto hear;
        }
        return int(last.length() - length);
        hear:;
    }
    return 0;
}

  那么我们应当如何找出长度最长的连接方式呢？这道题数据范围不大，我们直接枚举所有情况就可以了。

  接下来问题就变成了如何枚举所有情况，这种情况下，我们一般有两种选择：DFS和BFS。不过这题还是使用DFS简单一些，直接递归就可以了，BFS还需要手动复制数据，很麻烦。

  接下来写出代码就很简单了：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
int n;
string input[20];
int linked[20];

int simulate(const string& pre, const string& last) {
    for (int length = 1; length != pre.length(); ++length) {
        if (length >= last.length()) return 0;
        int i = int(pre.length() - length);
        for (int k = 0; k != length; ++k) {
            if (pre[i + k] != last[k]) goto hear;
        }
        return int(last.length() - length);
        hear:;
    }
    return 0;
}

// 连接一个新的字符串
// 参数：
//   pre - 当前列表末尾的字符串下标
//   plus - 要连接的新的字符串的下标
// 返回值：增长的长度
int link(int pre, int plus) {
    static int cache[20][20]{};
    int& flag = cache[pre][plus];
    if (flag == 0) flag = simulate(input[pre], input[plus]) + 1;
    return flag - 1;
}

// 参数：
//   length - 当前长度
//   pre - 末尾字符串的下标
// 返回值：最大长度
int dfs(int length, int pre) {
    int result = length;
    for (int i = 0; i != n; ++i) {
        if (linked[i] != 2) {
            int value = link(pre, i);
            if (value == 0) continue;
            ++linked[i];
            result = max(result, dfs(length + value, i));
            --linked[i];
        }
    }
    return result;
}

int main() {
    cin >> n;
    for (int i = 0; i != n; ++i) cin >> input[i];
    getchar();
    int start = getchar();
    int result = 0;
    for (int i = 0; i != n; ++i) {
        if (input[i][0] == start) {
            ++linked[i];
            result = max(result, dfs(int(input[i].length()), i));
            --linked[i];
        }
    }
    printf("%d\n", result);
    return 0;
}

目前不知道为什么，这个代码在洛谷上所有数据点全部WA了，但是其它平台是可以AC的

创作不易，扫描下方打赏二维码支持一下吧ヾ(≧▽≦*)o