Chinaunix首页 | 论坛 | 博客
  • 博客访问: 12331
  • 博文数量: 8
  • 博客积分: 415
  • 博客等级: 下士
  • 技术积分: 110
  • 用 户 组: 普通用户
  • 注册时间: 2009-02-20 23:38
文章分类

全部博文(8)

文章存档

2009年(8)

我的朋友
最近访客

分类: C/C++

2009-04-17 17:04:18

算法的基本思想:
当字符匹配的时候,不是简单的给相应元素赋上1,而是赋上其左上角元素的值加一。
我们用两个标记变量来标记矩阵中值最大的元素的位置,在矩阵生成的过程中来判断
当前生成的元素的值是不是最大的,据此来改变标记变量的值,那么到矩阵完成的时
候,最长匹配子串的位置和长度就已经出来了。
===========================================================================
程序:
#include
#define M 100
char* LCS(char left[],char right[])
{    //LCS问题就是求两个字符串最长公共子串的问题
    int lenLeft=strlen(left),lenRight=strlen(right),k;
    //获取左子串的长度,获取右子串的长度
    char*c=malloc(lenRight),*p;//注意这里要写成char型,而不是int型,否则输入整型数据时会产生错误。      //矩阵c纪录两串的匹配情况
    int start,end,len,i,j;//start表明最长公共子串的起始点,end表明最长公共子串的终止点
    end=len=0;//len表示最长公共子串的长度
    for(i=0;i    {    for(j=lenRight-1;j>=0;j--)//串2从后向前比较
        {    if(left[i] == right[j])//元素相等时
            {    if(i==0||j==0)
                    c[j]=1;
                else
                {    c[j]=c[j-1]+1;
                }
            }
            else
                c[j] = 0;
            if(c[j] > len)
            {    len=c[j];
                end=j;
            }
        }
    }
    start=end-len+1;
    p =(char*)malloc(len+1);//数组p纪录最长公共子串
    for(i=start; i<=end;i++)
    {    p[i-start] = right[i];
    }
    p[len]='\0';
    return p;
}
void main()
{    char str1[M],str2[M];
    printf("请输入字符串1:");
    gets(str1);
    printf("请输入字符串2:");
    gets(str2);
    printf("最长子串为:");
    printf("%s\n",LCS(str1,str2));
}
==========================================================================
程序测试:
输入
字符串1:21232523311324
字符串2:312123223445
数组c的变化情况为:
 0 0 1 0 1 0 1 1 0 0 0 0
 0 1 0 2 0 0 0 0 0 0 0 0
 0 0 2 0 3 0 1 1 0 0 0 0
 1 0 0 0 0 4 0 0 2 0 0 0
 0 0 1 0 1 0 5 1 0 0 0 0
 0 0 0 0 0 0 0 0 0 0 0 1
 0 0 1 0 1 0 1 1 0 0 0 0
 1 0 0 0 0 2 0 0 2 0 0 0
 1 0 0 0 0 1 0 0 1 0 0 0
 0 2 0 1 0 0 0 0 0 0 0 0
 0 1 0 1 0 0 0 0 0 0 0 0
 1 0 0 0 0 1 0 0 1 0 0 0
 0 0 1 0 1 0 2 1 0 0 0 0
 0 0 0 0 0 0 0 0 0 1 1 0
长:14(串1的长度),宽:12(串2的长度)
最长子串为:21232
阅读(1003) | 评论(0) | 转发(0) |
0

上一篇:没有了

下一篇:vsftpd mysql

给主人留下些什么吧!~~