首页 › 题库 › C/C++编程考级 › C/C++编程三级 › 简答题
简答题 偏难
#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 &lt;stdio.h&gt; #include &lt;string.h&gt; 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 &lt; strlen(p);i++){            if(!i){                for(j = t + k;j &lt; strlen(s);j++){                    if(s[j] == p[i]){                        k = 1;                        break;                    }                }                t = j;            }else{                 for(j++;j &lt; 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 &lt; min){             min = len;             m = t;             n = j;         }     }     for(i = m;i &lt;= n;i++) printf("%c", s[i]);     return 0; }</pre>
这道题暂未补解析。