A29782. 子串与子列
填空题
中等
知识点
题目描述
子串与子列
题目描述
子串是一个字符串中连续的一部分，而子列是字符串中保持字符顺序的一个子集，可以连续也可以不连续。例如给定字符串atpaaabpabtt，pabt是一个子串，而pat就是一个子列。
现在给定一个字符串S和一个子列P，本题就请你找到S中包含P的最短子串。若解不唯一，则输出起点最靠左边的解。
输入
输入在第一行中给出字符串S，第二行给出P。 S非空，由不超过10^4个小写字母组成；P保证是S的一个非空子列。
输出
在一行中输出S中包含P的最短子串。 若解不唯一，则输出起点最靠左边的解。
输入样例
atpaaabpabttpcat pat
输出样例
pabt
参考答案
#include<bits/stdc++.h>
using namespace std;
/*
思路：
找所有可能子串的开始位置
从开始位置往后找子列的长度
*/
int main() {
string s,p;
cin>>s>>p;
int min_len=s.size()+1,min_i=0;
//遍历字符串s
for(int i=0; i<s.size(); i++) {
if(s[i]==p[0]) {//找出字符串s和子串p的第一个字符相同的所有元素的下标
//接着找子串p剩余的字符
int cnt=0;//找出子列p的所有字符
for(int j=i; j<s.size()&&j-i<min_len; j++) { //从可能子串的第二个位置开始
if(s[j]==p[cnt]) cnt++; //找子列p的第0~p.size()-1个字符
if(cnt==p.size()) { //找完了
if(j-i<min_len) { //取最小值
min_len=j-i;
min_i=i; //记录最小值起点
}
break;
}
}
}
}
//输出子串
for(int i=min_i; i<=min_i+min_len; i++)
cout<<s[i];
return 0;
}
上一题
下一题