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 2406 Power Strings---KMP

Posted on 2009-08-29 05:00 Uriel 阅读(583) 评论(0)  编辑 收藏 引用 所属分类: POJ 、字符串处理
求一个字符串有几次匹配，KMP变形。。去东华前一天做出来时很高兴啊。。可惜那天看的另两道字符串都没出。
/*Problem: 2406  User: Uriel 
 Memory: 5100K  Time: 141MS 
 Language: C  Result: Accepted*/

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


int GetNextVal(char* Pattern, long next[]);
long Next[1000001];

char dest[1000001]; 
    
int main()
{
  long n,key;
  while(scanf("%s",dest)!=EOF)
  {
    if(dest[0]=='.')exit(0);
    n=strlen(dest);
    GetNextVal(dest,Next);
    key=n/(n-Next[n-1]);
    if(n%(n-Next[n-1])==0)printf("%d\n",key);
    else
        printf("1\n");
    memset(dest,0x00,sizeof(dest));
  }
    return 0;
}

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

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

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