PTA甲级——1177

1177 Subsequence in Substring

A substring is a continuous part of a string. A subsequence is the part of a string that might be continuous or not but the order of the elements is maintained. For example, given the string atpaaabpabtt, pabt is a substring, while pat is a subsequence.

Now given a string S and a subsequence P, you are supposed to find the shortest substring of S that contains P. If such a solution is not unique, output the left most one.

Input Specification:

Each input file contains one test case which consists of two lines. The first line contains S and the second line P. S is non-empty and consists of no more than 104 lower English letters. P is guaranteed to be a non-empty subsequence of S.

Output Specification:

For each case, print the shortest substring of S that contains P. If such a solution is not unique, output the left most one.

Sample Input:

1
2
atpaaabpabttpcat
pat

Sample Output:

1
pabt

思路

​ 题意：

​ 思路：可以使用最暴力的办法，暴力枚举匹配即可。我们这里使用模式化匹配的方式（实际上就是一个双指针的思路。稍微可以优化一点）

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#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;

}