子串是一个字符串中连续的一部分，而子列是字符串中保持字符顺序的一个子集，可以连续也可以不连续。例如给定字符串 atpaaabpabtt，pabt是一个子串，而 pat 就是一个子列。
现给定一个字符串 S 和一个子列 P，本题就请你找到 S 中包含 P 的最短子串。若解不唯一，则输出起点最靠左边的解。
输入格式：
输入在第一行中给出字符串 S，第二行给出 P。S 非空，由不超过 104 个小写英文字母组成；P 保证是 S 的一个非空子列。
输出格式：
在一行中输出 S 中包含 P 的最短子串。若解不唯一，则输出起点最靠左边的解。
输入样例：
atpaaabpabttpcat
pat
输出样例：
pabt
代码长度限制
16 KB
时间限制
300 ms
内存限制
64 MB
栈限制
8192 KB
一道伪装成乙级的甲级题(= =)
思路：首先，注意到子列和子串的首元素都是相同的，同时为了保证最短，则它们的尾元素也必须相同。那么我们可以以子列的首元素开始进行在字符串的遍历搜索，搜索直到字列元素都被遍历过一遍。
因为子串包含字子列，而给出了子列，那么我们只需要
1. 当枚举到子列的元素后，将已遍历子列的位置向后移动，直到对子列完全遍历；
2. 如果没有枚举到子列元素，就单纯向后枚举。在此期间无论是否枚举到，已遍历字符串的位置都会增加，用于形成子串；
3. 如果子列已经完全被遍历，那么记录这个字串的左右端点和端点差；
4. 对于端点差，如果下次的端点差大于本次的端点差，或者相同，那么我们都应该用本次的，直到出现更小的端点差。
具体细节在注释里给出。
#include <iostream>
#include <string>
using namespace std;
int main(){
string s;
string p;
cin >> s;
cin >> p;
int left=0,right=0; // 标定开始区间与结尾区间
int minn = 10000; // 记录开始与结尾区间之差的最小值
for(int i=0;i<s.length();i++){
if(s[i] == p[0]){ // 以子列的第一个元素作为字串的开头
int pos = 1; // pos = 0是子列的第一个，现遍历寻找第二个子列元素
// 开始循环遍历字符串，与子列匹配
for(int j = i + 1;j < s.length();j++){
// 如果区间比minn大的，直接忽略，因为我们要最小值
// 如果区间与minn相同，但已经有minn了，那么用之前的minn，即取左边的
if(minn <= j - i) continue;
if(s[j] == p[pos]) pos++; // 若有匹配到，则子列继续匹配下一个元素
if(pos == p.length()){ //子列所有元素全部匹配完毕，则记录左右区间
left = i;
right = j;
minn = j - i; // 标记为最小区间
break; // 本次匹配完成
}
}
}
}
// 将区间输出即可。
for(int i = left;i <= right;i++)
cout << s[i];
}代码验证无误。
