Uriel's Corner

Research Associate @ Harvard University / Research Interests: Computer Vision, Biomedical Image Analysis, Machine Learning
posts - 0, comments - 50, trackbacks - 0, articles - 594

POJ 3461 Oulipo---KMP

Posted on 2009-08-29 05:06 Uriel 阅读(468) 评论(0)  编辑 收藏 引用 所属分类: POJ字符串处理
KMP变形。。匹配了一次之后不退出。。加上Next的值继续比下去,直到串尾
/*Problem: 3461  User: Uriel 
  Memory: 1232K  Time: 125MS 
  Language: C  Result: Accepted
*/
 

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

int kmpMatch(char* Src, char* Pattern);
int GetNextdest(char* Pattern, int next[]);
int Next[10001];

int main()
{    
    
char source[1000001];
    
char dest[10001];
    
int i,n;
    scanf(
"%d",&n);
    
for(i=0;i<n;i++)
    
{
        memset(dest,
0x00,sizeof(dest));
        memset(source,
0x00,sizeof(source));
        scanf(
"%s",dest);    
        scanf(
"%s",source);    
        GetNextdest(dest,Next);
        printf(
"%d\n",kmpMatch(source, dest));
    }
    
    
return 0;
}


int kmpMatch(char* Src, char* Pattern)
{
    
int i=0,j=0;
    
int s_len,p_len;
    
int sum=0
    s_len
=strlen(Src);
    p_len
=strlen(Pattern);

flag: 
while(i<s_len && j<p_len)
{
    
if(j==-1||Src[i]==Pattern[j])
    
{
        
++i;   
        
++j;
    }

    
else
    
{
        j
=Next[j];      
    }

}

if (j==p_len && i<s_len){sum++;j=Next[j];goto flag;}
else if(j==p_len && i==s_len){sum++;return sum;}
else
    
return sum;
}


int GetNextdest(char* Pattern, int next[])
{
    
int i=1,j=0;
    
int p_len=strlen(Pattern);

    next[
0]=-1;
    
while(i<p_len)
    
{
        
if(Pattern[i]==Pattern[j]||j==-1)
        
{
            
++i;++j;
            
if(Pattern[i]!=Pattern[j])next[i]=j;
            
else
                next[i]
= next[j];
        }

        
else
            j
=next[j];
    }

    
return 0;
}


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理