用N个串中找到最短的公共串（不要求连续，仅仅要相对位置一样就可以）

迭代加深搜索就可以

剪枝：当前的深度＋最少还有加深的深度是否大于限制的长度，若是，则退回。

#include "stdio.h"

#include "string.h"

const char ch[10]="ATCG";

int deep,n;

char s[10][10];

int pos[10];//记录第i个序列正在使用第几个位置

int Max(int a,int b)

{

    if (a<b) return b;else return a;

}

int get_h()

{

    int ans,i;

    ans=0;

    for (i=0;i<n;i++)

        ans=Max(ans,strlen(s[i])-pos[i]);//找出在当前情况下最长的未被匹配的长度估測长度

    return ans;

}

int dfs(int w)

{

    int h,i,j,flag;

    int temp[10];

    h=get_h();

    if(w+h>deep) return 0;//当前长度+估測的长度比deep还大的话。也就没有继续往下搜索的必要了

    if(h==0) return 1;

    for (i=0;i<4;i++) //枚举当前位置的4个字母

    {

        flag=0;

        for (j=0;j<n;j++)

            temp[j]=pos[j];//先将pos保存起来

        for (j=0;j<n;j++)

            if (s[j][pos[j]]==ch[i])//当前这位符合。则该串的位置往后移一位

            {

                flag=1;

                pos[j]++;

            }

        if (flag==1)//有符合的，则往下搜索

        {

            if (dfs(w+1)==1) return 1;

            for (j=0;j<n;j++)//还原

                pos[j]=temp[j];

        }

    }

    return 0;

}

int main()

{

    int Case,i;

    scanf("%d",&Case);

    while (Case--)

    {

        scanf("%d",&n);

        deep=0;

        for (i=0;i<n;i++)

        {

            scanf("%s",s[i]);

            deep=Max(deep,strlen(s[i]));

            pos[i]=0;

        }

        while (1)

        {

            if (dfs(0)==1) break;

            deep++;

        }

        printf("%d\n",deep);

    }

    return 0;

}