这道题,一个亲提示后,我百度了一下,据说是微软面试题。。基础测试不造为毛要考
lcs算法
- #include<stdio.h>
- #include<string.h>
- voidmain()
- {
- char *x="aabcdababce";
- char *y="12abcabcdace";
- int m=strlen(x);
- int n=strlen(y);
- int i,j,k,l;
- int maxlength=0;
- int start=0;
- int count=0;//用来判断是否匹配的变量
- for(i=1;i<=n;i++)//匹配长度的循环
- for(j=0;j<n-i+1;j++)//y的起始位置的循环
- for(k=0;k<m-i+1;k++)//x的起始位置的循环
- {
- count=0;
- for(l=0;l<i;l++)//判断是否匹配,代码可以优化
- if(y[j+l]==x[k+l])
- count++;
- if(count==i&&i>maxlength)
- {
- maxlength=i;//记录最大长度
- start=j;//记录最大长度的起起位置
- }
- }
- if(maxlength==0)
- printf("NoAnswer");
- else
- for(i=0;i<maxlength;i++)
- printf("%c",y[start+i]);
- }
复制代码
这是百度大神百科出来的,我表示接受无能。
又找到了几篇博客,原理是两个字符串一个做行一个做列,组成个矩形进行比较。相同的置1,不同的置0
"nbitheimanb”和“itheia
n b i t h e i m a n b
i 0 0 1 0 0 0 1 0 0 0 0
t 0 0 0 1 0 0 0 0 0 0 0
h 0 0 0 0 1 0 0 0 0 0 0
e 0 0 0 0 0 1 0 0 0 0 0
i 0 0 1 0 0 0 1 0 0 0 0
a 0 0 0 0 0 0 0 0 1 0 0
可是如果只置1的话要查找也很麻烦,所以大神们又想出来了优化。如果两个字符相同的话,就把他左上角的数字加1
n b i t h e i m a n b
i 0 0 1 0 0 0 1 0 0 0 0
t 0 0 0 2 0 0 0 0 0 0 0
h 0 0 0 0 3 0 0 0 0 0 0
e 0 0 0 0 0 4 0 0 0 0 0
i 0 0 1 0 0 0 5 0 0 0 0
a 0 0 0 0 0 0 0 0 1 0 0
大家可以根据这个思路试着写一下。
|
|