1125 子串与子列 – PAT乙级真题

子串是一个字符串中连续的一部分，而子列是字符串中保持字符顺序的一个子集，可以连续也可以不连续。例如给定字符串 atpaaabpabtt，pabt是一个子串，而 pat 就是一个子列。

现给定一个字符串 S 和一个子列 P，本题就请你找到 S 中包含 P 的最短子串。若解不唯一，则输出起点最靠左边的解。

输入格式：

输入在第一行中给出字符串 S，第二行给出 P。S 非空，由不超过 104 个小写英文字母组成；P 保证是 S 的一个非空子列。

输出格式：

在一行中输出 S 中包含 P 的最短子串。若解不唯一，则输出起点最靠左边的解。

输入样例：

atpaaabpabttpcat
pat

输出样例：

pabt

分析：使用point表示当前待匹配的P串中下标，MIN表示目前获得的最短的答案长度（其实应该是j-i+1，但是只需要大小比较的话统一减1也不影响，可以少一次+1的计算）。ansl和ansr分别表示最终答案的最左和最右端点。
遍历整个S字符串，当前字符为P的首字符的时候，开始第二重循环，查看以当前位置作为起点是否存在一个子串满足条件。如果j-i等于MIN了，可以直接跳出循环，因为我就算当前情况满足题意，也不如用之前的那个子串（因为之前的那个子串起点更靠左）。如果point已经到了P的长度，表示所有内容匹配成功，并且当前最优，将现在的i和j更新成为新的答案～

#include <iostream>
using namespace std;
int main() {
    int point, MIN = 10000, ansl = 0, ansr = 0;
    string S, P;
    cin >> S >> P;
    for (int i = 0; i <= S.size() - P.size(); i++) {
        if (S[i] == P[0]) {
            point = 1;
            for (int j = i + 1; j < S.size(); j++) {
                if (j - i== MIN) break;
                if (S[j] == P[point]) point++;
                if (point == P.size()) {
                    ansl = i, ansr = j;
                    MIN = j - i ;
                    break;
                }
            }
        }
    }
    for (int i = ansl; i <= ansr; i++) cout << S[i];
    return 0; 
}

#include <iostream>

using namespace std;

int main() {

int point, MIN = 10000, ansl = 0, ansr = 0;

string S, P;

cin >> S >> P;

for (int i = 0; i <= S.size() - P.size(); i++) {

if (S[i] == P[0]) {

point = 1;

for (int j = i + 1; j < S.size(); j++) {

if (j - i== MIN) break;

if (S[j] == P[point]) point++;

if (point == P.size()) {

ansl = i, ansr = j;

MIN = j - i ;

break;

}

for (int i = ansl; i <= ansr; i++) cout << S[i];

return 0;

}

❤ 点击这里 -> 订阅《PAT | 蓝桥 | LeetCode学习路径 & 刷题经验》by 柳婼

❤ 点击这里 -> 订阅《从放弃C语言到使用C++刷算法的简明教程》by 柳婼

❤ 点击这里 -> 订阅PAT甲级乙级、蓝桥杯、GPLT天梯赛、LeetCode题解离线版