7-2 Subsequence in Substring (25 分)
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 10^4 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
题目限度
题目粗心
给定两个字符串 S 和 P,输入蕴含 P 的最短 S 子串, 如果有多个, 那么就输入最右边的那个.
算法思路
应用双指针进行暴力搜寻, 咱们应用指针 i 搜寻字符串 S 不回退,指针 j 搜寻字符串 P 会回退,同时应用 end 标记以后字符串 S 与 P[j]待比拟的地位,初始为 i +1,如果 s[end] == p[j],那么就 ++end,++j。否则就 ++end。如果最初 j 来到 P 的结尾地位,阐明以后 S 的子串 [i,end) 蕴含字符串 P,应用 minLen 记录其最短长度,同时如果在遍历的时候发现以后 [i,end) 的长度 end- i 曾经大于 minLen 了,就阐明就算前面有解也不是最优解,间接退出即可。
提交后果
AC 代码
#include<cstdio>
#include<vector>
#include<iostream>
#include<algorithm>
using namespace std;
int main() {
string s, p;
cin >> s >> p;
int n = s.size();
int m = p.size();
int minLen = 0x3fffffff;
string ans;
for (int i = 0; i < n; ++i) {
// 起始位不同肯定不行
if (s[i] != p[0]) {continue;}
int j = 1;
int end = i + 1;
// 判断 [i,end) 的子串是否有子序列 b
while (j < m && end < n) {if (s[end] == p[j]) {
++end;
++j;
} else {++end;}
// 以后子串的长度曾经长于已保留的记录,就不须要持续判断了
if (end - i >= minLen) {break;}
}
// [i,end)的子串含有子序列 b
if (j == m) {
int len = end - i;
if (len < minLen) {ans = s.substr(i, len);
minLen = len;
}
}
}
cout << ans;
return 0;
}