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:
atpaaabpabttpcatpatSample 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;}