首页 诗词 字典 板报 句子 名言 友答 励志 学校 网站地图
当前位置: 首页 > 教程频道 > 开发语言 > C语言 >

查找最长匹配单词,希望得到大家的建议,多谢

2012-11-09 
【分享】查找最长匹配单词,希望得到大家的建议,谢谢s[]This is C programmer plaintextt[]This is a p

【分享】查找最长匹配单词,希望得到大家的建议,谢谢
s[]="This is C programmer plaintext";
t[]="This is a plaintext for C programming";
要求就是查找上面两个字符串里面的最长匹配单词。
很久没写C了,折腾了老半天,勉强实现了功能。
感觉还是很差,贴出来希望得到各位的建议,谢谢。

C/C++ code
#include<stdio.h>#include<string.h>#define LONG 100#define SHORT 50int is_sub_str(char *p_long, char * p_short){    int len_long=strlen(p_long), len_short=strlen(p_short);    int i, j;    for(i=0;i<=len_long-len_short;i++){        for(j=0;j<len_short;j++)            if(p_long[i+j]!=p_short[j])  //逐个扫描是否匹配                break;        if(j>=len_short)  //子串是否扫描完成            break;    }    if((i==0 || p_long[i-1]==' ') && (p_long[i+j]==' ' || p_long[i+j]=='\0')){        if(i<=len_long-len_short)  //疑惑,这里的两个if语句,先后顺序不一样,结果不一样,希望得到解答            return 1;  //说明是子串且是单词    }else        return 0;}void main(){    char s[]="This is C programmer plaintext";    char t[]="This is a plaintext for C programming";    char temp_word[50], max_word[50]=" ";    int i, n;    for(i=0,n=0;s[i]!='\0';i++){  //提取单词        if(s[i]!=' ')            temp_word[n++]=s[i];        if(s[i+1]==' ' || s[i+1]=='\0'){            temp_word[n]='\0';            n=0;            if(is_sub_str(t, temp_word))                if(strlen(temp_word)>strlen(max_word))                    strcpy(max_word, temp_word);        }    }    printf("The longest same word of the two strings is: %s\n", max_word);}


[解决办法]
其实简言之,就是 最长公共子串问题 哈

先看代码吧:

C/C++ code
/* 最长公共子串 DP */int dp[30][30]; void LCS_dp(char * X, int xlen, char * Y, int ylen){    maxlen = maxindex = 0;    for(int i = 0; i < xlen; ++i)    {        for(int j = 0; j < ylen; ++j)        {            if(X[i] == Y[j])            {                if(i && j)                {                    dp[i][j] = dp[i-1][j-1] + 1;                }                if(i == 0 || j == 0)                {                    dp[i][j] = 1;                }                if(dp[i][j] > maxlen)                {                    maxlen = dp[i][j];                    maxindex = i + 1 - maxlen;                }            }        }    }    outputLCS(X);}//copyright @ahathinking 

热点排行