子串是一个字符串中连续的一部分，而子列是字符串中保持字符顺序的一个子集，可以连续也可以不连续。例如给定字符串 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];}

代码验证无误。