AcWing 778. 字符串最大跨距(c++不调用库函数,有注释)
原题链接
困难
作者:
九里今天学点什么呢
,
2021-04-20 17:05:28
,
所有人可见
,
阅读 401
#include<iostream>
#include<string>
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");return 0;}
else{
//求最左边的终止点,从0开始匹配
//先求最左边的起始点
int l=0;
while(l+s1.size()<=s.size()){
int k=0;
while(k<s1.size()){//k表示目前匹配到s1的哪一位
if(s1[k]!=s[l+k]){break;}//不匹配时不改变k
k++;
}
if(k==s1.size())break;//s最左边的一个s1子串匹配时跳出
l++;//如没找到匹配点,起点加一
}
l=l+s1.size()-1;
//求最右边的起始点
int r=s.size()-s2.size();
while(r>=0){
int k=0;
while(k<s2.size()){
if(s2[k]!=s[r+k]){break;}
k++;
}
if(k==s2.size())break;
r--;
}
if(l>r){puts("-1");return 0;}
else{
cout<<(r-l-1)<<endl;
}
}
}