问题:
http://acm.pku.edu.cn/JudgeOnline/problem?id=1936思路:
第一个思路是搜索，然后直接写代码:
1 void
2 search(int depth, int start_from)
3 {
4 int i;
5 char ch;
6 char *ptr, *rt;
7 if(depth == sub_len) {
8 mark = 1;
9 return;
10 }
11 ch = sub[depth];
12 ptr = seq;
13 while(!mark && ((rt=strchr(ptr+start_from, ch))!=NULL)) {
14 search(depth+1, rt-seq+1);
15 ptr = rt+1;
16 }
17 }
结果上述代码RE，想着即使不RE，估计也得TLE
看了别人代码，发现原来可以这么简单:
1 #include<stdio.h>
2 #include<stdlib.h>
3 #include<string.h>
4 #define MAX_LEN 100001
5 char sub[MAX_LEN], seq[MAX_LEN];
6 int sub_len, seq_len;
7
8 int
9 main(int argc, char **argv)
10 {
11 char *sub_p, *seq_p;
12 while(scanf("%s %s", sub, seq) != EOF) {
13 sub_len = strlen(sub);
14 seq_len = strlen(seq);
15 for(sub_p=sub, seq_p=seq; sub_p<sub+sub_len && seq_p<seq+seq_len; )
16 if(*sub_p == *seq_p) {
17 ++sub_p;
18 ++seq_p;
19 } else
20 ++seq_p;
21 if(sub_p == sub+sub_len)
22 printf("Yes\n");
23 else
24 printf("No\n");
25 }
26 }