题目描述

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

现在，我们想要检测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

缺点1：在读入这个字符串 讲其转化为 3个字符串不够简洁
可以将其改进为：

（方法一）string s, s1, s2;
    char c;
    while (cin >> c, c != ',') s += c;
    while (cin >> c, c != ',') s1 += c;
    while (cin >> c) s2 += c;

(方法二) string s,s1,s2;
    getline(cin,s,',');
    getline(cin,s1,',');
    getline(cin,s2,'\n');

缺点2：自己在查找第二个字符串的时候从前往后查找 会浪费时间
可以改进为从后往前找 使得代码更加高效

C++ 代码

#include <iostream>
using namespace std;
int main(){
    string str;
    getline(cin,str);
    int a[2]={0};
    for(int i=0,j=0;i<str.size();i++){
        if(str[i] == ','){
            a[j]=i;
            j++;
        }
    }
    string s  = str.substr(0,a[0]);
    string s1 = str.substr(a[0]+1,a[1]-a[0]-1);
    string s2 = str.substr(a[1]+1);
    int p1=0,p2=0;
    bool flag1=false,flag2=false;
    for(int i=0;i<s.size();i++){
        for(int j=i,cnt=0,k=0;j <s.size();j++){
            if(s[j] == s1[k++] ) cnt++;
            else break;
            if (cnt == s1.size()){
                p1 = i + s1.size() ; 
                flag1 = true;
                break;
            }
        }
        if(flag1) break;
    }
    for(int i=0;i<s.size();i++){
        for(int j=i,cnt=0,k=0; j < s.size() ; j++ ){
            if(s[j] == s2[k++] ) cnt++;
            else break;
            if (cnt == s2.size()){
                p2 = i ;
                flag2 = true;
                break;
            }
        }
    }
    int outcome=p2-p1;
    if(flag1 == false || flag2==false || p1>=p2 ) cout << "-1" << endl;
    else cout << outcome << endl;
    return 0;
}