1177 Subsequence in Substring – PAT甲级真题

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:

atpaaabpabttpcat
pat

Sample Output:

pabt

题目大意：子串是一个字符串中连续的一部分，而子列是字符串中保持字符顺序的一个子集，可以连续也可以不连续。例如给定字符串atpaaabpabtt，pabt是一个子串，而pat就是一个子列。现给定一个字符串S和一个子列P，本题就请你找到S中包含P的最短子串。若解不唯一，则输出起点最靠左边的解。

分析：使用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题解离线版