许多程序会大量使用字符串。对于不同的字符串,我们希望能够有办法判断其相似程序。我们定义一套操作方法来把两个不相同的字符串变得相同,具体的操作方法为:
修改一个字符(如把“ a”替换为“ b”);
增加一个字符(如把“ abdd”变为“ aebdd”);
删除一个字符(如把“ travelling”变为“traveling”);
比如,对于“ abcdefg”和“abcdef”两个字符串来说,我们认为可以通过增加 /减少一个“g”的方式来达到目的。上面的两种方案,都仅需要一次。把这个操作所需要的次数定义为两个字符串的距离,而相似度等于“距离 +1”的倒数。也就是说, “abcdefg”和“abcdef”的距离为 1,相似度为 1/2=0.5。给定任意两个字符串,你是否能写出一个算法来计算它们的相似度呢?
这个题目其实就是最长相似子串LCS算法。具体参阅
http://blog.chinaunix.net/uid-26456800-id-3366849.html
- #include <stdlib.h>
- #include <stdio.h>
- #include <string.h>
- #define MAX 1000
- #define min(a,b) ((a)<(b)?(a):(b))
- int test(char* a, char *b){
- int asize = strlen(a);
- int bsize = strlen(b);
- int result[MAX][MAX] = {{0}};
- int i = 0;
- for(;i<asize;i++){
- result[0][i] = (a[i] == b[0] ? 0:1);
- }
- for(i=0;i<bsize;i++){
- result[i][0] = (a[0] == b[i] ? 0:1);
- }
- int row, col;
- for(row = 1; row<bsize; row++){
- for(col = 1; col<asize; col++){
- int t1, t2, t3;
- t1 = result[row-1][col-1] + (a[row] == b[col] ? 0 : 1);
- t2 = result[row][col-1] + 1;
- t3 = result[row-1][col] + 1;
- result[row][col] = min(t3, min(t1,t2));
- }
- }
- printf("%d \n", result[row-1][col-1]);
- return(result[row-1][col-1]);
- }
- int main(){
- char a[] = "abc";
- char b[] = "abd";
- test(a,b);
- }
阅读(1143) | 评论(0) | 转发(2) |