P1019题解单词接龙（c++ 求两字符串最短重叠字串）

Yuleo_

已于 2023-02-06 23:16:31 修改

阅读量355

点赞数 1

分类专栏：算法题解文章标签： c++ 深度优先算法

于 2023-01-16 16:54:42 首次发布

本文链接： https://blog.csdn.net/jj6666djdbbd/article/details/128706055

版权

算法题解专栏收录该内容

31 篇文章 2 订阅

订阅专栏

文章介绍了如何使用贪心算法来解决P1019单词接龙问题，重点在于找到两个字符串之间的最小重叠子串，以形成最长的连接字符串。提供了两种不同的方法实现检查最小重叠子串，并进一步讨论了如何通过深度优先搜索（DFS）遍历所有字符串，计算多个字符串的最长长度，同时确保每个字符串使用不超过两次。

摘要由CSDN通过智能技术生成

P1019 单词接龙

洛谷传送门：
添加链接描述

本题重点：利用贪心思想，得到的合成的字符串长度最长，则这两个字符串一定存在最小的重叠字串，这样才是最长的。

求每个字符串之间的最小重叠子串以使得一个字符串可以追加在另一个字符串的末尾，从而形成一条 ”龙“字符串

现在的问题？
如何求得两个字符串的最小重叠子串

方法一：

int check(string str1,string str2)
{   
	//得到两个字符串的最短长度
    for (int i=0;i<min(str1.length(),str2.length());i++)
    {
        bool fg=true;
        //根据
        for (int j=0;j<=i;j++)
        {
            if (str1[str1.length()-i+j-1]!=str2[j])
            {
                fg=false;
            }
        }
        //如果fg为true，说明在这一次遍历中存在一个最短重叠子串，直接返回 i+1（i+1为这个子串的长度）
        if (fg) return i+1;
    }
    return 0;   //无最小重叠部分
}

方法二：注意 i 的值等细节不一样

int check(string str1,string str2)
{   
    for (int i=1;i<min(str1.length(),str2.length());i++)
    {
        bool fg=true;
        for (int j=0;j<i;j++)
        {
            if (str1[str1.length()-i+j]!=str2[j])
            {
                fg=false;
            }
        }
        if (fg) return i;
    }
    return 0;   //无最小重叠部分
}

接下来的问题：如何求得多个字符串的最长长度？

dfs遍历每一个字符串。依次求出每一个字符串之间的最小重叠子串，并且在dfs开始时进行长度的统计，取最大长度值，当字符串的出现次数多于两次时则跳过这个字符串，继续遍历下一个字符串，执行相同的操作，另外还需要进行回溯，以便可以求出求出所有的可能情况。

完整代码：

#include<bits/stdc++.h>
using namespace std;

int n,c;
const int SIZE=25;
vector<string> s(SIZE);
int vis[SIZE]; 
int res=0;
/*
check: 得到两个字符串的最小重叠子串的长度
*/
int check(string str1,string str2)
{   
    for (int i=0;i<min(str1.length(),str2.length());i++)
    {
        bool fg=true;
        for (int j=0;j<=i;j++)
        {
            if (str1[str1.length()-i+j-1]!=str2[j])
            {
                fg=false;
            }
        }
        if (fg) return i+1;
    }
    return 0;   //无最小重叠部分
}
void dfs(string str,int len)
{
    //更新最大长度
    res=max(res,len);
    for (int i=0;i<n;i++)
    {
        if (vis[i]>=2) continue;            //该字符串使用次数需要小于2次
        int num=check(str,s[i]); //获取最小重叠子串的长度
        if (num>0) 
        {
            vis[i]++;
            dfs(s[i],len+s[i].length()-num);
            vis[i]--;					//回溯
        }   
    }
}
int main()
{
	cin>>n;
    for (int i=0;i<=n;i++)
    {
        cin>>s[i];
    }
    //n为开始字符，长度默认为1
    dfs(s[n],1);    
    cout<<res;
	return 0;
}

....................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................