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 閱讀(597) 評論(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;

}

只有注冊用戶登錄后才能發表評論。
【推薦】100%開源！大型工業跨平臺軟件C++源碼提供，建模，組態！

相關文章: POJ 3450 Corporate Identity---KMP or strstr or Suffix Array POJ 3613 Cow Relays---Floyd+矩陣相乘 POJ 1625 Censored!---AC 自動機+DP+高精度 POJ 3250 Bad Hair Day---棧的應用 POJ 3759 Simple Distributed computing system---最大流 POJ 1851 Map---計算幾何 POJ 1380 Equipment Box && POJ 2172 Bricks---計算幾何 POJ 2284 That Nice Euler Circuit---計算幾何 POJ 1931 Biometrics---計算幾何 POJ 3129 How I Wonder What You Are!----計算幾何

網站導航: 博客園 IT新聞 BlogJava 博問 Chat2DB 管理

Uriel's Corner

導航

留言簿(9)

文章分類(1191)

文章檔案(594)

搜索

積分與排名

最新評論

POJ 2406 Power Strings---KMP