【字符串】字符串相似度（大小写敏感问题）（有起点的部分片段遍历）

问题描述
最长公共子串指给定的两个字符串之间最长的相同子字符串（忽略大小写），最长公共子串长度可用来定义字符串相似度。
现给出两个字符串S1和S2，S1的长度为Len1，S2的长度为Len2，假设S1和S2的最长公共子串长度为LCS，则两个字符串的相似度定义为2LCS/(Len1+Len2)。
例如：S1=”App”，S2=”apple”，S1长度为3，S2长度为5，它们的最长公共子串为”App”，长度为3，则相似度为23/(3+5)=0.75。
现给出两个字符串，请计算它们的相似度结果保留3位小数。

输入说明
输入为两行，分别表示两个字符串S1和S2，每个字符串长度不超过100个字符，所有字符均为可打印字符，包括大小写字母，标点符号和空格。

输出说明
输出两个字符串的相似度，结果四舍五入保留3位小数。

输入样例
App
Apple

输出样例
0.750
.
.
.
我们需要先解决几个问题:
①大小写不敏感（即不区分大小写）：
如果我们在主要程序中嵌入类似于if( x-y = = 32 || x = = y)这样的判断语句，程序将变得比较复杂，可读性也差。既然大小写不敏感，索性把输入的全部转成大写或小写，这个过程用函数实现也可：

void to_upper(char a[],int n)
<-------------to_upper(a,101)
{
int i;
for (i=0; i<=n-1; i++)
{
if (a[i]>='a' && a[i]<='z')
{
*(a+i)-=32;
}
}
}

向函数中传递数组并通过指针修改值的相关知识，再此不做赘述。
***当然有的题目会要求选择性打开大小写敏感，那么就判断一下，在插入函数。请看：
（比如输入的a=1时大小写敏感，a=0时不敏感）

if (a==1)
;
else if (a==0) {to_upper(&x,101);}
else
;

②判断相同的片段，判断是否为最长相同串：
当找到第一个相同的字符，扫描头先停下。创建两个临时扫描头tempi和tempj，往后扫描至字符不一样位置，记录下长度sum。与maxsum比较，判断是否为最长。请看：

for (i=0; i<=len1-1; i++)
{
for (j=0; j<=len2-1; j++)
{
if (y[j]==x[i])
//检索到第一个相同的字母
{
int tempi=i,tempj=j;
//tempi,tempj分别往后扫描
while(y[tempj]==x[tempi] && y[tempj]!='' && x[tempi]!='')
{
sum++;
tempj++;
tempi++;
}
if (sum>=summax)
summax=sum;
//判断是否最长
}
else
;
sum=0;
}
}

需要注意到几个小细节：
（1）每次内循环最后，sum必须归零。
（2）判断相等的if语句只有y[tempj]==x[tempi]是不够的，还需要临时扫描头没扫到句末的null。（这个点卡了我好久！！！如果不加这一句的话，有时summax的值会偏大。比如输入a和a，summax理论上是1，但是会计算出2）。

③为了保证结果的准确性，最后计算时把summax、len1、len2全部强制转换为double类型。
.
.
.
请看完整代码：

#include<stdio.h>
#include<string.h>
#include<ctype.h>
void to_upper(char a[],int n)
{
int i;
for (i=0; i<=n-1; i++)
{
if (a[i]>='a' && a[i]<='z')
{
*(a+i)-=32;
}
}
}
int main(void)
{
char x[101];
char y[101];
gets(x);
gets(y);
int len1=strlen(x);
int len2=strlen(y);
to_upper(&x,101);
//不区分大小写，索性全转化成大写
to_upper(&y,101);
int i,j;
int sum=0;
//记录当前的公共串长
int summax=0; //记录最长公共子串
//puts(x);
检验是否转为大写
//puts(y);
for (i=0; i<=len1-1; i++)
{
for (j=0; j<=len2-1; j++)
{
if (y[j]==x[i])
//检索到第一个相同的字母
{
int tempi=i,tempj=j;
//tempi,tempj分别往后扫描
while(y[tempj]==x[tempi] && y[tempj]!='' && x[tempi]!='')
{
sum++;
tempj++;
tempi++;
}
if (sum>=summax)
summax=sum;
//判断是否最长
}
else
;
sum=0;
}
}
//printf("summax=%d len1=%d len1=%dn",summax,len1,len2);
//检验数据正确性
double outcome;
outcome=(2*(double)summax)/((double)len1+(double)len2);
printf("%.3f",outcome);
return 0;
}

最后

以上就是自信秀发最近收集整理的关于【字符串】字符串相似度（大小写敏感问题）（有起点的部分片段遍历）的全部内容，更多相关【字符串】字符串相似度（大小写敏感问题）（有起点内容请搜索靠谱客的其他文章。