标题
字符串相似度
类别
字符串处理
时间限制
1S
内存限制
256Kb
问题描述
最长公共子串指给定的两个字符串之间最长的相同子字符串（忽略大小写），最长公共子串长度可用来定义字符串相似度。
现给出两个字符串S1和S2，S1的长度为Len1，S2的长度为Len2，假设S1和S2的最长公共子串长度为LCS，则两个字符串的相似度定义为2*LCS/(Len1+Len2)。
例如：S1=”App”，S2=”apple”，S1长度为3，S2长度为5，它们的最长公共子串为”App”，长度为3，则相似度为2*3/(3+5)=0.75。
现给出两个字符串，请计算它们的相似度结果保留3位小数。
输入说明
输入为两行，分别表示两个字符串S1和S2，每个字符串长度不超过100个字符，所有字符均为可打印字符，包括大小写字母，标点符号和空格。
输出说明
输出两个字符串的相似度，结果四舍五入保留3位小数。
输入样例
App
Apple
输出样例
0.750
#include<stdio.h>
#include<string.h>
#include<math.h>
int main()
{int LCS=0,i,j;int sim[100][100]={0};double Len1,Len2,a;char S1[100],S2[100];gets(S1);gets(S2);Len1=strlen(S1);Len2=strlen(S2);for(i=0;i<Len1;i++){for(j=0;j<Len2;j++){if(S1[i]==S2[j]||abs(S1[i]-S2[j])==32){if(i!=0&&j!=0){sim[i][j]=sim[i-1][j-1]+1;}elsesim[i][j]=1;}}}for(i=0;i<Len1;i++){for(j=0;j<Len2;j++){if(sim[i][j]>LCS)LCS=sim[i][j];}}a=2.0*LCS/(Len1+Len2);printf("%.3lf",a);return 0;
}