【PAT甲级】1177 Subsequence in Substring（25分）[判断子序列，暴力，双指针]

问题思考：

• 用字符串暴力匹配的思路，能过。
• 用模式串匹配母串，扫描一遍母串，只要模式串第一位匹配上，就往后判断保住子序列所需子串的长度（判断子序列可以用双指针法）。
• 过程中间记录最短的符合要求的子串。比较更新，最后输出结果即可。

代码实现：

#include<cstring>
#include<iostream>
using namespace std;

int main() {
    string s, p;
    cin >> s >> p;
    int n = s.length(), m = p.length();
    string ans = s;    // 存储子串
    int l = n;    // 记录子串的长度
    for (int i = 0; i <= n - m; i++) {
        // 每次遇到子序列的起点，就往后判断子串所需长度
        if (s[i] == p[0]) {
            string sub = "";
            int j = i, k = 0; // 双指针法判断子序列
            while (k < m) {
                if (s[j] == p[k]) k++;
                sub += s[j];
                j++;
            }
            if (l > sub.size()) {    // 记录长度最小的子串
                ans = sub;
                l = ans.size();
            }
        }
    }
    cout << ans;
    return 0;
}