描述
用一个字符串表示一段基因，例如：“CTATGGGTTT”。两段基因的相似度定义为它们所包含的最大公共子串的长度。例如：“CCTTGG”和“TGGGC”的最大公共子串为“TGG”，它的长度为3，则我们称“CCTTGG”和“TGGGC”的相似度为3。现给定两段基因，要求计算它们的相似度。
关于输入
输入第一行包含一个正整数N（0
关于输出
对于每组测试数据输出一行，该行包含一个整数，表示给定基因段的相似度。
例子输入
2

CCCCC TTTTTGGGGGCC

ACTGGG DDD

例子输出
2

0

提示
提示，这里表示基因的字母个数可能不只是C、T、A、G这四个字母。

===关于输入===
用一个字符串表示一段基因，例如：“CTATGGGTTT”。两段基因的相似度定义为它们所包含的最大公共子串的长度。例如：“CCTTGG”和“TGGGC”的最大公共子串为“TGG”，它的长度为3，则我们称“CCTTGG”和“TGGGC”的相似度为3。现给定两段基因，要求计算它们的相似度。

===关于输出===
对于每组测试数据输出一行，该行包含一个整数，表示给定基因段的相似度。

我的程序：
#include <stdio.h>
#include <string.h>
#define min(x,y) (x<y?x:y)
int main()
{
    int N;
    scanf("%d",&N);
    getchar();
    int i,j,t,m,num=0,max=0;
    char s1[401],s2[401];
    for(i=0;i<N;i++)
    {
        scanf("%s %s",s1,s2);
        int len1=strlen(s1);
        int len2=strlen(s2);
        for (j=0;j<len1;j++)
        {
            for(t=0;t<len2;t++)
            {
                num=0;
                if(s1[j]==s2[t])
                {
                int k= min(len2-t,len1-j);
                for(m=0;m<=k;m++)
                {
                    while (s1[j+m]==s2[t+m])
                       num++;
                }
                if(num>max)
                    max=num;
                }
            }
        }
        printf("%d\n",max);
    }
    return 0;
}
程序运行无结果
Empty
为什么呢？

试了一下，没细测。

#include <stdio.h>
#include <string.h>

int _closely(char *s, char *s2)
{
    char *p, *p2;
    int max=0;
    for (p2=s2+strlen(s2); p2>s2&&(p2-s2)>max; --p2)
    {
        *p2 = '\0';
        for (p=s2; *p&&(p2-p)>max; ++p)
            if (strstr(s,p))
                max = (p2-p);
    }
    return max;
}

main()
{
    char s1[100], s2[100];
    int i, n;
    printf("测试次数：");
    scanf("%d", &n);
    for (i=0; i<n; ++i)
    {
        printf("比对字串1：");
        scanf("%s", s1);
        printf("比对字串2：");
        scanf("%s", s2);
        printf("相似度为: %d\n\n", _closely(s1,s2));
    }
}

strstr比较失败则可以跳出循环进行第一次比较了吧~感觉高效的是一个嵌套的KMP算法~把strstr看成是KMP算法的对字符的单次匹配~虽然我知道快速算法思路~不过KMP我还没有掌握~

PS:对哦~知道strstr就不必要知道KMP算法了~
因为下一个字符不能成功匹配就可以跳过当前成功匹配字符串的长度~

[此贴子已经被作者于2017-11-4 18:36编辑过]

另外感觉重写KMP算法或者在strstr成功找到后再改写的效率应该比单纯调用strstr的效率要高一点~因为匹配成功后可以直接找到结果和下一个字符比较而用strstr的正常来说会重新开始比较~

PS:感觉最为高效还是三楼所说的二重KMP算法~

PS:好像字符串子串成功匹配的越多匹配效率越高~
最慢情况竟然是相似度为0的时候~时间复杂度为o(s1*s2)~挺神奇的~

[此贴子已经被作者于2017-11-4 19:03编辑过]

https://bbs.bccn.net/thread-476674-1-1.html

曾经的一条难题,在受到这题的启发后,看来这个帖子的确可以找到时间复杂度为o(n^3)的解法~

搜寻子串的算法已是现成，以前也提过Sunday算法。没看过strstr源码，不清楚其算法。
这问题的搜寻子串，关键是先要获取可能最长的子串，再去搜寻。
所以效率体现在获取可能最长的子串的过程，如果可分段处理效率会高些。
如，比对串有无效字符（对方不存在的字符），可以拆开分段处理获取可能最长的子串。

嗯,说得也对,不过看这个二楼这个代码算法不存在剪枝现象,也就是说无论最终结果的子串是多长都不影响算法执行效率,属于比较开始就可以确认比较次数的算法。之所以重新写一个算法会比strstr的效率会高是因为正常来说每一次成功搜索的结果已经作为一个参数返回了,每一次都是一个独立的过程,而针对这题的快速算法是上次成功搜索仍然在上次成功的基础上进行,然而已知KMP算法匹配失败是通过next数组进行回溯。也可以说这题匹配算法是整个连续的过程,用strstr把过程作为分割点效率会比连续处理的理论上会低一点~

当然sunday算法肯定是可以的,就是看看执行效率如何~或者有兴趣的可以去尝试一下~

[此贴子已经被作者于2017-11-4 22:08编辑过]

https://zhidao.baidu.com/question/1734722239460016707.html?device=mobile&ssid=0&from=0&uid=0&pu=usm@0,sz@1320_1002,ta@qbase_2_5.1_2_12137.1&bd_page_type=1&baiduid=1DB0A820D8E1223ADB8D447E968E6154&tj=tc

然后很无语地发现strstr竟然是用朴素的匹配方法~当然追求效率的重写一个KMP算法是很有必要的~

是的，2楼的代码算法也是“朴素的匹配方法”，没有考虑效率的问题。
提到效率问题，6楼就吹一下。

效率的东西，有时是相对来说的。视实际情况，有时对于一些特殊情况，用朴素的算法好读好理解，且效率是可以接受。
提到sunday算法是个人喜欢sunday算法的简洁明快，也试过用sunday算法写模拟strstr()。