| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 482 人关注过本帖
标题:KMP算法求解,当输入定位pos=0时,定位正确,pos=1或其他时,定位就不正确了 ...
只看楼主 加入收藏
小跳蚤
Rank: 10Rank: 10Rank: 10
等 级:青峰侠
威 望:1
帖 子:437
专家分:1623
注 册:2011-4-9
结帖率:89.66%
收藏
已结贴  问题点数:30 回复次数:5 
KMP算法求解,当输入定位pos=0时,定位正确,pos=1或其他时,定位就不正确了,希望高手解答,谢谢
程序代码:
#include <stdio.h>
#include <string.h>
void get_next(char t[],int *next);
int index_KMP(char s[],char t[],int *next ,int pos);

 int main ()

 {
    char s[]="abcabcaaabcacacc";
    char t[]="abcac";
    int next[100]={0};
    int pos;                 //pos用来输入s字符串开始定位的位置
    int k=0;
    printf("please input the start position:pos\n");
    scanf("%d",&pos);
    get_next(t,next);
    for(int i=0;i<10;i++)
        printf("%d",next[i]);
    k=index_KMP(s,t,next,pos);
    if(k!=0)
        printf("the first position is%d\n",k);
    else
        printf("can not find");
    return 0;

 }
int index_KMP(char s[],char t[],int *next ,int pos)//利用KMP算法定位
{
    int i=pos;
    int j=0;
    while(i<strlen(s) && j<strlen(t))
    {
        if(j==-1||s[i]==t[j])
        {
            ++i;
            ++j;
        }
        else
        {
            j=next[j];
        }
    }
    if(j>=strlen(t))
        return i-strlen(t)+1;
    else
        return 0;
}
void get_next(char t[],int *next)//获取next数组中的数值
{
    int i=0;
    int j=-1;
    next[0]=-1;
    while(i<strlen(t))
    {
        if(j==-1||t[i]==t[j])
        {
            ++i;
            ++j;
            next[i]=j;
        }
        else
        {
            j=next[j];
        }
    }
}

搜索更多相关主题的帖子: 定位 pos color 
2012-04-13 14:34
草狼
Rank: 9Rank: 9Rank: 9
等 级:蜘蛛侠
威 望:2
帖 子:577
专家分:1040
注 册:2010-4-6
收藏
得分:15 
把 strlen() 提到循环外面先求求值

如:
int index_KMP(char s[],char t[],int *next ,int pos)//利用KMP算法定位
{
    int i=pos;
    int j=0;
    int len = strlen(t);
    int lens = strlen(s);
    while(i<lens && j<len)
    {
        if(j==-1||s[i]==t[j])
        {
            ++i;
            ++j;
        }
        else
        {
            j=next[j];
        }
    }
    if(j>=len)
        return i-strlen(t)+1;
    else
        return 0;
}
2012-04-13 14:54
laoyang103
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
来 自:内蒙古包头
等 级:贵宾
威 望:19
帖 子:3082
专家分:11056
注 册:2010-5-22
收藏
得分:15 
去做下北航的1016 一切都解决了

http://www.

[ 本帖最后由 laoyang103 于 2012-4-13 16:17 编辑 ]

                                         
===========深入<----------------->浅出============
2012-04-13 16:16
小跳蚤
Rank: 10Rank: 10Rank: 10
等 级:青峰侠
威 望:1
帖 子:437
专家分:1623
注 册:2011-4-9
收藏
得分:0 
回复 2楼 草狼
明白了,多谢啦
2012-04-13 18:43
小跳蚤
Rank: 10Rank: 10Rank: 10
等 级:青峰侠
威 望:1
帖 子:437
专家分:1623
注 册:2011-4-9
收藏
得分:0 
回复 3楼 laoyang103
版主算法一定好牛X怎么学的啊
2012-04-13 18:44
小跳蚤
Rank: 10Rank: 10Rank: 10
等 级:青峰侠
威 望:1
帖 子:437
专家分:1623
注 册:2011-4-9
收藏
得分:0 
回复 3楼 laoyang103
程序代码:
laoyang103大哥,我做了一下1001题超级最小公倍数,运行的和他说的一样的啊,为什么还说我编译错误啊

#include <stdio.h>
struct date
{
    __int64 a;
    __int64 b;
}s[10];
int main()
{
    __int64 tmp=0;
    int i=-1;
    do
    {
        i++;
        scanf("%I64d%I64d",&s[i].a,&s[i].b);
    }while(s[i].a!=0 && s[i].b!=0);
    for(int j=0;j<i;j++)
    {
        if(s[j].a<s[j].b)
        {
            __int64 temp=s[j].a;
            s[j].a=s[j].b;
            s[j].b=temp;
        }
        __int64 m=s[j].a , n=s[j].b;
        while(s[j].b!=0)
        {
            tmp=s[j].a%s[j].b;
            s[j].a=s[j].b;
            s[j].b=tmp;
       
        }
        printf("%I64d\n",m*n/s[j].a);
    }

}
   
        
2012-04-13 19:01
快速回复:KMP算法求解,当输入定位pos=0时,定位正确,pos=1或其他时,定位就不 ...
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.017748 second(s), 7 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved