终曲

2
abcd
ab
bc
abc
ab
bd

abc
No
题目大意：给出一个主字符串，再给两个段的字符串，看着两个字符串是不是包含在主字符串里边，如果包含则输出最短		  的包含两个段字符串的子串，否则输出No。思路：这题对我这种菜鸟还真是难，开始想的是用kmp算法，但是bbbbcbb  b  c 这种情况就不知道怎么办了，不能输出最短的		，因为kmp返回的是第一个匹配的位置。苦苦理解大神代码，惊叹不已，用两个for循环，把所有的符合的情况都比较了		一下，然后输出符合条件的，大神的代码原本使用的是传统的BF字符匹配算法，我鉴于刚学kmp就改了一下，下边是代码		煮是地方就是比较核心的地方，向大神致敬。2014.11.26
#include <stdio.h>
#include <string.h>
char ans[110] ;
char s1[110], s2[110], s3[110] ;
char ss[110] ;
int next[110];
void getnext(char s[]){//kmp算法求next数组的值 
	int i,j,len=strlen(s);
	i=0;j=-1;
	next[i]=j;
	while(i<len){
		if(j==-1||s[i]==s[j]){
			++i;++j;
			next[i]=j;
		}
		j=next[j];
	}
}
int kmp(char s[], char p[]){//kmp算法核心 
    int i, j, len1 = strlen(s), len2 = strlen(p) ;
    getnext(p);
    i=j=0;
    while(i<len1&&j<len2){
    	if(j==-1||s[i]==p[j]){
    		++i;++j;
    	}
    	else j=next[j];
    }
    if(!p[j]) return 1;//当子串比较完毕 
    else return 0;
 }
int test(){
    if (kmp(ss,s2) == 0) return 0;
    if (kmp(ss,s3) == 0) return 0;
    return 1;
}
int main (){
     int T, i, j;
     scanf("%d", &T);
     while(T--){
         scanf("%s%s%s",s1,s2,s3);
         strcpy(ans,"No");//用一个ans数组来做临时储存的字符数组 
         for(i=0;s1[i];i++){//这两个循环很巧妙，i++可以让主串的每次都去掉第一个字母，看看是否还匹配
		 	 for(j=i;s1[j];j++){ //如果还匹配，那么原来的就不是最短的子串，还要继续进行下边 
                 ss[j-i]=s1[j];
                 ss[j-i+1]='\0';
                 if(test()){
                     if (strcmp(ans,"No")==0||strlen(ss)<strlen(ans)||strcmp(ss,ans)<0)
                         strcpy(ans,ss);//输出的结果要保证最短子串，还要是字典排序即bc不能是cb，最后的结果存入ans里边 
                    break;
                 }
             }
         }
        puts(ans);
     }
     return 0;
 }