/*
一个串的“子序列”(subsequence)是将这个串中的一些字符提取出来得到一个新串，并且不改变它们的相对位置关系。例如，串"XDoi","XianYu!","TaiQiangLa!","loa"都是串"XianYuDalaoTaiQiangLa!"的子序列。 我们说串t是串s1和s2的公共子序列，当且仅当t是s1的子序列且t是s2的子序列。定义串s1和s2的相似度为它们最长公共子序列的长度。 现在给定一个文本串S和一组模式串T[1]、T[2]、……、T[n]。求T[i]中和S具有最高相似度的那个，然后输出最高的相似度。S和所有的T[i]都只含有小写字母。 输入规则：先是一行字符串S。第二行是n(1<=n<=100)。第三行以降的n行是n个模式串T[1]...T[n]。S和所有的T[i]的长度都不超过2000. Sample Input:
abcdef 4 acfaff appont emmm bdxeuf Sample Output:
bdxeuf 4 Description:
串abcdef和bdxeuf的最长公共子序列是bdef，长度为4.
*/ #include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int M=; int result[]; /*
void match(char *a,char *b,int s,int t,int i)
{
int x=s;
int y=t;
while(a[x]!='\0')
{
while(b[y]!='\0')
{
if(a[x]==b[y])
{
result[i]++;
match(a,b,x+1,y+1,i);
cout<<b[y]<<endl;
}
y++;
}
x++;
} }
*/ void match(char *a,char *b,int s,int t,int i)
{
int x=;
for(s=;a[s]!='\0';s++)
{
for(t=x;b[t]!='\0';t++)
{
if(a[s]==b[t])
{
result[i]++;
x++;
//cout<<b[t]<<endl;
break;
}
}
}
} /*
bool compare(int a,int b)//降序为>
{
return a>b;
}
*/
int main()
{
char a[M];
char b[][M];
memset(a,'\0',sizeof(a));
int n; while(scanf("%s",&a))
{
memset(b,'\0',sizeof(b));
memset(result,,sizeof(result));
cin>>n;
for(int i=;i<n;i++)
scanf("%s",&b[i]);
for(int i=;i<n;i++)
{
match(a,b[i],,,i);
//cout<<"result:"<<result[i]<<";"<<b[i]<<endl;
}
/*
sort(result,result+n,compare);
cout<<result[0]<<endl;
memset(a,'\0',sizeof(a));
*/
int max=result[];
int max_num=;
for(int i=;i<n;i++)
{
if(result[i]>max)
{
max_num=i;
max=result[i];
}
}
cout<<b[max_num]<<endl<<max<<endl;
memset(a,'\0',sizeof(a));
} return ;
}
代码运行说明：
tz@HZAU
2019/3/7