简答题
偏难
#7536
子串与子列 子串是一个字符串中连续的一部分,而子列是字符串中保持字符顺序的一个子集,可以连续也可以不连续。例如给定字符串 atpaaabpabtt,pabt 是…
子串与子列
子串是一个字符串中连续的一部分,而子列是字符串中保持字符顺序的一个子集,可以连续也可以不连续。例如给定字符串 atpaaabpabtt,pabt 是一个子串,而 pat 就是一个子列。
现给定一个字符串 S 和一个子列 P,本题就请你找到 S 中包含 P 的最短子串。若解不唯一,则输出起点最靠左边的解。
时间限制:1000
内存限制:65536
输入
输入在第一行中给出字符串 S,第二行给出 P。S 非空,由不超过 104 个小写英文字母组成;P 保证是 S 的一个非空子列。
输出
在一行中输出 S 中包含 P 的最短子串。若解不唯一,则输出起点最靠左边的解。
样例输入
atpaaabpabttpcat pat
样例输出
pabt
答案与解析
正确答案:<pre class="brush:cpp;toolbar:false">#include <stdio.h>
#include <string.h>
int main(){
char s[10001], p[10001];
int i, j, t = 0, len, min = 10001, m, n, k = 0, flag = 0;
scanf("%s\n%s", s, p);
while(1){
for(i = 0;i < strlen(p);i++){
if(!i){
for(j = t + k;j < strlen(s);j++){
if(s[j] == p[i]){
k = 1;
break;
}
}
t = j;
}else{
for(j++;j < strlen(s);j++){
if(s[j] == p[i]) break;
}
}
if(j == strlen(s)){
flag = 1;
break;
}
}
if(flag == 1) break;
len = j - t + 1;
if(len < min){
min = len;
m = t;
n = j;
}
}
for(i = m;i <= n;i++) printf("%c", s[i]);
return 0;
}</pre>
这道题暂未补解析。