AcWing 778. 字符串最大跨距
原题链接
困难
作者:
liangjj
,
2021-01-18 17:44:03
,
所有人可见
,
阅读 372
#include<iostream>
using namespace std;
int main(){
string s,s1,s2;
char c;
while(cin>>c,c!=',') s=s+c;
while(cin>>c,c!=',') s1=s1+c;
while(cin>>c) s2=s2+c;
//返回-1的情况:
//s1或s2中任何一个长度大于s;
//没有找到s1或者s2
//找到了s1和s2,但是他们存在重合部分,求不出最大跨距
if(s1.size()>s.size() || s2.size()>s.size()){
cout<<"-1"<<endl;
return 0;
}
else{
/*s1*/
int m=0;//取开始
while(m+s1.size()-1<=s.size()-1){//右端点下标值不能超过s.size()-1
//开始匹配s1
int k=0;
while(k<s1.size()){
if(s1[k]==s[m+k]) k++;//对应的字符相等,继续比较下一个
else break;//对应字符不相等,直接跳出
}
if(k==s1.size()) break;
m++;
}
/*s2*/
int n=s.size()-1;
while(n-s2.size()+1>=0){//左端点下标值不能低于0
//开始匹配s2
int k=0;
while(k<s2.size()){
if(s2[s2.size()-1-k]==s[n-k]) k++;
else break;
}
if(k==s2.size()) break;
n--;
}
//分别得到s1右端点和s2左端点
int x1=m+s1.size()-1;
int x2=n-s2.size()+1;
int d=x2-x1-1;
if(d<=0) cout<<"-1"<<endl;
else cout<<d<<endl;
}
return 0;
}