778. 字符串最大跨距

目录

一、问题描述

二、解题

1.解题思路

2.代码

一、问题描述

有三个字符串 S,S1,S2其中，S 长度不超过 300300，S1和 S2 的长度不超过 1010。

现在，我们想要检测 S1 和 S2 是否同时在 S 中出现，且 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

二、解题

1.解题思路

2.代码

#include
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");// 第三步：若有解，则找s1和s2的位置else{// 1.枚举s1的起点int l = 0;while(l + s1.size() <= s.size()){int k = 0;while(k < s1.size()){if(s[l+k] != s1[k]) break;k++;}if(k==s1.size()) break; // 当k与s1的长度一致时，说明匹配到了l++;    //更新起点}// 2.枚举s2的起点int r = s.size() - s2.size();while( r >= 0){int k = 0;while(k < s2.size()){if(s[r+k] != s2[k]) break;k++;}if(k==s2.size()) break;r--;}// 第四步：s1的最后一个位置和s2的第一个位置l += s1.size()-1;   // s1的最后一个位置if(l >= r) puts("-1");  //如果l大于r，则说明s1不是严格在s2的左边else printf("%d\n", r-l-1);}return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！