刷题刷出新高度，偷偷领先！偷偷领先！偷偷领先！ 关注我们，悄悄成为最优秀的自己！
简答题
4.子串和子列
子串是一个字符串中连续的一部分，而子列是字符串中保持字符顺序的一个子集，可以连续也可以不连续。例如给定字符串 atpaaabpabtt，pabt 是一个子串，而 pat 就是一个子列。
现给定一个字符串 S 和一个子列 P，本题就请你找到 S 中包含 P 的最短子串。若解不唯一，则输出起点最靠左边的解。
时间限制：1000
内存限制：65536
输入
输入在第一行中给出字符串 S，第二行给出 P。S 非空，由不超过 104 个小写英文字母组成；P 保证是 S 的一个非空子列。
输出
在一行中输出 S 中包含 P 的最短子串。若解不唯一，则输出起点最靠左边的解。
样例输入
atpaaabpabttpcat
pat
样例输出
pabt
子串是一个字符串中连续的一部分，而子列是字符串中保持字符顺序的一个子集，可以连续也可以不连续。例如给定字符串 atpaaabpabtt，pabt 是一个子串，而 pat 就是一个子列。
现给定一个字符串 S 和一个子列 P，本题就请你找到 S 中包含 P 的最短子串。若解不唯一，则输出起点最靠左边的解。
时间限制：1000
内存限制：65536
输入
输入在第一行中给出字符串 S，第二行给出 P。S 非空，由不超过 104 个小写英文字母组成；P 保证是 S 的一个非空子列。
输出
在一行中输出 S 中包含 P 的最短子串。若解不唯一，则输出起点最靠左边的解。
样例输入
atpaaabpabttpcat
pat
样例输出
pabt
使用微信搜索喵呜刷题，轻松应对考试！
答案：
解析：
本题要求找到字符串中包含特定子列的最短子串，且如果存在多个解，需要输出起点最靠左边的解。可以使用滑动窗口算法来解决这个问题。首先遍历字符串S，找到子列P在S中第一次出现的位置，然后以这个位置为中心，向两边扩展窗口，直到找到包含P的最短子串。在这个过程中，需要记录最小窗口的起始位置和结束位置。最后输出对应的最短子串即可。需要注意的是，如果存在多个解，需要继续向左移动窗口的起始位置，直到找到最靠左的解为止。
创作类型：
原创
本文链接：4.子串和子列子串是一个字符串中连续的一部分，而子列是字符串中保持字符顺序的一个子集，可以连续也可以
版权声明：本站点所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明文章出处。让学习像火箭一样快速，微信扫码，获取考试解析、体验刷题服务，开启你的学习加速器！
分享考题 
