P1019 [NOIP2000 提高组] 单词接龙

2023-12-23 06:08:33

题目链接

P1019 [NOIP2000 提高组] 单词接龙

细节

题目中描述的在两个单词相连时,其重合部分合为一部分具有一定的误导性,对于字符串 b e e bee bee e e d eed eed ,合并之后的字符串为 b e e e d beeed beeed ,只有中间的 e e e 为重复部分。故应该求两个字符串的最小重叠长度,这样才能构建一个最大长度的字符串。

思路

为何要使用深度优先搜索

为了求得最大长度的字符串,需要多次遍历所有字符串,每次有多种选择,就像一颗不断发散的树枝一样,这就需要使用深度优先搜索。

剪枝

假设有 n n n 个字符串,每个字符串最多能两次添加到最终字符串里,故时间复杂度为 O ( 2 n ? 2 n ) = O ( 4 n 2 ) O(2n * 2n) = O(4n^2) O(2n?2n)=O(4n2) ,故需要使用剪枝来优化。假如两个字符串没有重叠部分,则不再往深处搜索,这就是剪枝。此外,还应该定义一个数组 u s e [ ] use[] use[] 来表示字符串使用的次数,如果使用次数等于两次,则跳过当前字符串。

dfs函数的实现

d f s dfs dfs 函数用于在字符串数组 s t r s [ ] strs[] strs[] 中寻找给定字符串 s t r str str 的下一个待拼接的字符串,而且还有一个参数 l e n N o w lenNow lenNow 表示当前已拼接的字符串的长度。

每次先更新答案,如果 l e n N o w lenNow lenNow 更大,就把 l e n N o w lenNow lenNow 赋值给答案。
然后在循环中判断 s t r s [ ] strs[] strs[] 中哪个字符串与 s t r str str 重叠,如果能找到,而且使用次数不超过两次,就增加使用次数,然后进行递归,传入该字符串和新的拼接字符串的长度,接着在回溯时减少使用次数(因为回溯时放弃使用该字符串),最后判断下一个符合要求的字符串,直到找到最大长度。在实现中可以先判断使用次数是否超过两次,这样减少了无效的判断重叠部分。

显然, d f s dfs dfs 函数需要另一个函数 g e t O v e r l a p L e n getOverlapLen getOverlapLen 来计算两个字符串重叠部分的最小长度,这个函数很容易实现:
先得到两个字符串 s 1 , s 2 s1, s2 s1,s2 的长度 l e n 1 , l e n 2 len1, len2 len1,len2 ,然后去较小值为 l i m lim lim l i m lim lim 用于防止数组下标越界。
每次循环中判断 s 1 s1 s1 的倒数第 j j j 个字符是否与 s 2 s2 s2 的第 j j j 个元素相等,如果不相等就退出循环,得到一个表示最大重叠长度 j j j
为了求得最小重叠长度,需要再嵌套一层循环,外层循环用于增加判断的字符数量 i i i ,内层循环用于判断 s 1 s1 s1 的倒数第 j j j 个字符是否与 s 2 s2 s2 的第 j j j 个元素相等,如果不相等就终止内层循环,然后返回已判断为相等的字符数量 i i i ,这点看代码会更好理解。

代码

#include <iostream>
#include <string>
using std::cin, std::cout, std::string;
const int N = 25;// 字符串数组的大小
string strs[N];// 用于存放字符串
/*
    n是字符串的个数
    len是拼接字符串的长度
    use[i]表示下标为i的字符串使用的次数
*/
int n, len, use[N];
// 求s1和s2字符串的最小重叠长度
int getOverlapLen(string s1, string s2) {
    int len1 = s1.length(), len2 = s2.length();	// 求得s1和s2的长度
    int lim = len1 < len2 ? len1 : len2;		// 求得s1和s2长度的较小值
    for (int i = 1; i <= lim; i++) {			// 外层循环用于控制比较多字符长度
        bool isEqual = true;					// 判断两个字符串的重叠长度是否为i
        for (int j = 0; j < i; j++) {			// 判断两个字符串的字符是否重叠
            if (s1[len1 - i + j] != s2[j]) {	// 如果字符不重叠
                isEqual = false;				// 则两个字符串的重叠长度不为i
                break;							// 中断内层循环
            }
        }
        if (isEqual) {							// 如果两个字符串的重叠长度为i
            return i;							// 返回i
        }
    }
    return 0;									// 两个字符串没有重叠部分,返回0
}
// 在字符串数组strs[]中寻找给定字符串str的下一个待拼接的字符串
void dfs(string str, int lenNow) {
    len = len > lenNow ? len : lenNow;		// 更新拼接字符串的长度
    for (int i = 0; i < n; i++) {
        if (use[i] == 2) {					// 如果当前字符串的使用次数等于两次
            continue;						// 跳过当前字符串
        }
        // 获取 已拼接字符串 和 下标为i的字符串 的重叠长度
        int ol = getOverlapLen(str, strs[i]);
        if (ol > 0) {						// 如果重叠长度大于0
            use[i]++;						// 使用下标为i的字符串
            // 寻找下一个待拼接字符串
            dfs(strs[i], lenNow + strs[i].length() - ol);
            use[i]--;						// 回溯时该字符串没被使用
        }
    }
}
int main() {
    cin >> n;
    for (int i = 0; i <= n; i++) {
        cin >> strs[i];						// 下标为n的字符串保存了指定开头的字母
    }
    dfs(strs[n], 1);						// 开头为指定字母,长度为1
    cout << len;
    return 0;
}

文章来源:https://blog.csdn.net/qq_61350148/article/details/135162231
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。