付翔的专栏
在鄙视中成长 记录成长的点滴
posts - 106,  comments - 32,  trackbacks - 0
今天碰见一个赤裸裸的 kmp 算法的题 直接找了个模板 但是却一直WA
后来 查自己的数据结构的书 改动一下
    //if( pat[j] > 0) return -2;
    
//else return i-j;
    return ((j==b)?(i-b) :-2);
后来就过了 郁闷 确实对于kmp 算法不是很熟啊
很是杯具

# include<stdio.h>
# include
<string.h>
int fail[10000+1];
long a,b;
int kmp(int* str, int* pat){
    
int i, j, k;
    memset(fail, 
-1sizeof(fail));
    
//fail[0] = 0;
    for (i = 1; i<b; ++i) {
        
for (k=fail[i-1]; k>=0 && pat[i]!=pat[k+1];k=fail[k]);
        
if (pat[k + 1== pat[i]) fail[i] = k + 1;
        
//if(k == 0)  fail[i] = k + 1;
    }
    i 
= j = 0;
    
while( i< a && j < b ){ // By Fandywang
        if( pat[j] == str[i] ) ++i, ++j;
        
else if(j == 0)++i;//第一个字符匹配失败,从str下个字符开始
        else j = fail[j-1]+1; }
    
//if( pat[j] > 0) return -2;
    
//else return i-j;
    return ((j==b)?(i-b) :-2);
}
int src[1000000+1];
int dest[10000+1];
int main()
{
    
int T,i;
    
    freopen(
"1284.txt","r",stdin);
    scanf(
"%d",&T);
    
while(T--)
    {
        scanf(
"%ld%ld\n",&a,&b);
        
for(i = 0; i < a; i ++)
            scanf(
"%d",&src[i]);
       
// src[i] = '\0';
        for(i = 0; i < b; i ++)
            scanf(
"%d",&dest[i]);
       
// dest[i] = '\0';
        printf("%d\n",kmp(src,dest)+1);
        
        
    }
    
return 0;
}


posted on 2010-07-26 19:42 付翔 阅读(593) 评论(2)  编辑 收藏 引用 所属分类: ACM 数据结构

FeedBack:
# re: hdu 1711 kmp 算法
2010-07-30 18:34 | smztsmzt
请教一下 关于串匹配的KMP算法问题

KMP中的主串指针不用回溯,下面的串匹配怎么进行:请教一下
位数: 1 2 3 4 5
主串: a a a a b
模式串: a a a b

如果主串指针不用回溯,可以发现主串包含模式串么?想不明白。
  回复  更多评论
  
# re: hdu 1711 kmp 算法
2010-08-02 13:21 | 付翔
@smztsmzt
KMP 算法 是没有回溯的
  回复  更多评论
  

只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理



<2010年9月>
2930311234
567891011
12131415161718
19202122232425
262728293012
3456789

常用链接

留言簿(2)

随笔分类

随笔档案

文章分类

文章档案

CSDN - 我的blog地址

博客

搜索

  •  

最新评论

阅读排行榜

评论排行榜