每日算法刷题Day10-字符串最大跨距、最长公共字符串后缀
每日算法刷题Day10-字符串最大跨距、最长公共字符串后缀
CSDN话题挑战赛第2期 参赛话题：算法题解
⭐每日算法题解系列文章旨在精选重点与易错的算法题，总结常见的算法思路与可能出现的错误，与笔者另一系列文章有所区别，并不是以知识点的形式提升算法能力，而是以实战习题的形式理解算法，使用算法。 🔥本文已收录于算法刷题系列专栏： 每日算法题解 欢迎订阅，持续更新。
文章目录
31.字符串最大跨距
有三个字符串 S,S1,S2，其中，S 长度不超过 300，S1 和 S2的长度不超过 10。
现在，我们想要检测 S1 和 S2 是否同时在 SS 中出现，且 S1 位于 S2 的左边，并在 S 中互不交叉（即，S1 的右边界点在 S2 的左边界点的左侧）。
计算满足上述条件的最大跨距（即，最大间隔距离：最右边的 S2 的起始点与最左边的 S1 的终止点之间的字符数目）。
如果没有满足条件的 S1，S2 存在，则输出−1。
例如，S= abcd123ab888efghij45ef67kl,S1= ab, S2= ef，其中，S1 在 S 中出现了 2 次，S2 也在 S 中出现了 2 次，最大跨距为：18。
输入格式
输入共一行，包含三个字符串 S,S1,S2，字符串之间用逗号隔开。
数据保证三个字符串中不含空格和逗号。
输出格式
输出一个整数，表示最大跨距。
如果没有满足条件的 S1 和 S2 存在，则输出 −1。
输入样例：
abcd123ab888efghij45ef67kl,ab,ef输出样例：
18思路
分别两次匹配字符串，s1从左向右匹配，s2从右向左匹配。再根据情况分别判断即可。重点在练，多敲几遍。
#include<bits/stdc++.h>
using namespace std;
int main()
{
string s,s1,s2;
char c;
while(cin >> c, c != ',')s += c;
while(cin >> c, c != ',')s1 += c;
while(cin >> c)s2 += c;
if(s.size()<s1.size() || s.size() < s2.size())puts("-1");
else{
int l = 0;
for(;l + s1.size() <= s.size();l++)
{
int k = 0;
for(; k < s1.size();k++)
{
if(s[l + k] != s1[k])break;
}
if( k == s1.size())break;
}
//s2从右向左找
int r = s.size() - s2.size();
for(; r >= 0 ;r--)
{
int k = 0;
for(; k < s2.size();k++)
{
if(s[r+ k] != s2[k])break;
}
if( k == s2.size())break;
}
l += s1.size() - 1;
if(l >= r)puts("-1");
else printf("%d\n", r - l - 1);
return 0;
}
}32.最长公共字符串后缀
给出若干个字符串，输出这些字符串的最长公共后缀。
输入格式
由若干组输入组成。
每组输入的第一行是一个整数 N。
N 为 0 时表示输入结束，否则后面会继续有 N 行输入，每行是一个字符串（字符串内不含空白符）。
每个字符串的长度不超过 200。
输出格式
共一行，为 N 个字符串的最长公共后缀（可能为空）。
数据范围
1≤N≤200
输入样例：
3
baba
aba
cba
2
aa
cc
2
aa
a
0输出样例：
ba
a思路
伪代码如下
for( 枚举后缀长度)
for(所有字符串)
for(枚举str[0]与str[i]的n个字符)代码
#include<bits/stdc++.h>
using namespace std;
const int N = 200;
int n;
string str[N];
int main()
{
while(cin >> n, n)
{
int len = 1000;
for(int i = 0; i < n; i++)
{
cin >> str[i];
if(str[i].size() < len)len = str[i].size();
}
for(;len;len--)
{
bool success = true;
for(int i = 0; i < n; i++)
{
bool is_same = true;
for(int j = 1; j <= len ; j++)
{
if( str[0][str[0].size() - j ] != str[i][str[i].size()- j])
{
is_same = false;
break;
}
}
if(!is_same)
{
success = false;
break;
}
}
if(success)break;
}
cout << str[0].substr(str[0].size() - len )<<endl;
}
return 0;
}
腾讯云开发者
