C++實例:求N個字符串的最長公共子串

字號:

求N個字符串的最長公共子串,N<=20,字符串長度不超過255。
    例如:N=3,由鍵盤依次輸入三個字符串為
    What is local bus ?
    Name some local buses.
    local bus is a high speed I/O bus close to the processer.
    則最長公共子串為"local bus"。
    #include
    #include
    #define MAX_N 20 //字符串的數(shù)目
    #define MAX_LEN 256 //字符串的長度(含結(jié)束符'\0')
    int N;//輸入的字符串?dāng)?shù)
    char str[MAX_N][MAX_LEN];//保存所有字符串
    int Len[MAX_N];//保存字符串的長度
    //字符串匹配,成功返回1,失敗返回0
    int str_match(char *s1, char *s2, int len)
    {
    while(len > 0)
    {
    if(*s1 != *s2)
    return 0;
    s1++;
    s2++;
    len --;
    }
    return 1;
    }
    //main
    void main()
    {
    int i,s,t,l;
    printf("請輸入字符串的數(shù)目N(N<=20):");
    scanf("%d",&N);
    gets(str[0]);
    printf("請輸入%d個字符串(每個字符串以回車結(jié)束):\n",N);
    for(i=0; i    {
    gets(str[i]);
    Len[i] = strlen(str[i]);
    }
    for(l=Len[0]; l>0; l--)
    {
    for(s=0; s+l-1 < Len[0]; s++)
    {
    int flag1 = 1;
    for(i=1; i    {
    int flag2 = 0;
    for(t=0; t+l-1 < Len[i]; t++)
    {
    if(str_match(str[0]+s,str[i]+t,l))
    {
    flag2 = 1;
    break;
    }
    }
    //失敗
    if(!flag2)
    {
    flag1 = 0;
    break;
    }
    }
    //成功
    if(flag1)
    {
    goto L;//跳到輸出
    }
    }
    }
    //輸出最長公共子串
    printf("最長公共子串為:");
    L: for(i=0; i    {
    printf("%c",*(str[0]+s+i));
    }
    printf("\n");
    }