加密字符串相似度计算

Question

现有4个加密的字符串(中间不含空格)，需要分析研究它们的相似度，两个字符串的相似度用其最长公共子系列的长度表示，例如，字符串“ABDECFG”和字符串“ADCGEFA”的一个最长公共子序列为 “ADEF”，所以这两个字符串的相似度为4。现在需要对输入的4个字符串，分别计算它们的相似度，找出相似度最高的一对字符串，若存在多对相似度最高的字符串，应全部输出。

【输入】 分4行输入4个字符串。

【输出】 按行依次输出相似度最高的一对字符串、它们的相似度、对应的最长公共子序列，若有多组最高相似度相同，应全部输出。

【输入样例】

ABDECFEB

ADCEBGH

ADCFEB

BECEBFBD

【输出样例】

ABDECFEB ADCFEB 6 ADCFEB

输出样例说明：以上4个字符串，共可以构成6组，依次计算它们的相似度如果，因此，相似度最高的是字符串ABDECFEB和ADCFEB，相似度为6，对应的一个最长公共子序列为ADCFEB。

ABDECFEB ADCEBGH 5 ADCEB

ABDECFEB ADCFEB 6 ADCFEB

ABDECFEB BECEBFBD 5 BECFB

ADCEBGH ADCFEB 5 ADCEB

ADCEBGH BECEBFBD 3 CEB

ADCFEB BECEBFBD 3 CFB

Answer 1

C语言代码如下：

#include <stdio.h>
#include <string>
struct StXypoint
{
	int x;
	int y;
};
//获取两个字符串的相似度
void Xsd(char* p1,char* p2,char* p3,int &n)
{
	int len1 = strlen(p1);
	int len2 = strlen(p2);
	int i,j;
	bool b;
	n = 0;
	
	for (i = 0; i < len1; i++)
	{
		b = false;
		//判断p1[i]是否在p2中
		for (j = 0; j < len2; j++)
		{
			if (p1[i] == p2[j])
			{
				b = true;
				break;
			}
		}
		if (b) //如果在p2中
		{
			b = false;
			//判断是否已经统计过
			for (j = 0; j < n;j++)
			{
				if (p3[j] == p1[i])
				{
					b = true;
					break;
				}
			}
			if (!b)
			{
				p3[n] = p1[i];
				n++;
			}
		}
	}
}

void main()
{
	char buf[4][50] = {0};   //保存输入字符
	char pout[6][50] = {0};  //保存相似度字符串
	int nmb[6] = {0};        //保存相似度
	struct StXypoint pt[6];  //保存下标
	int i,j,t;
	int index = 0;
	int maxindex = 0;
	int maxNmb;
	printf("请输入4个字符串\n");
	for (i = 0; i < 4; i++)
	{
		scanf("%s",buf[i]);
	}
	//计算相似度
	for(i = 0;i < 4;i++)
	{
		for (j = i+1; j < 4;j++)
		{
			Xsd(buf[i],buf[j],pout[index],nmb[index]);
			pt[index].x = i;
			pt[index].y = j;
			index++;
		}
	}
	//找相似度最大的
	maxNmb = nmb[0];
	for (i = 1; i < 6; i++)
	{
		if (nmb[i] > maxNmb)
		{
			maxNmb =nmb[i];
		}
	}
	//遍历所有最大
	for (t = 0; t < 6; t++)
	{
		if(nmb[t] == maxNmb)
		{
			i = pt[t].x;
			j = pt[t].y;
			printf("%s  %s  %d  %s\n",buf[i],buf[j],nmb[t],pout[t]);
		}
	}
	
	
}