首页 > 代码库 > hdu2087剪花布条(KMP)
hdu2087剪花布条(KMP)
题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=2087
和hdu1686几乎一样,一点需要注意细节,已在代码中注明。
1 #include<cstdio> 2 #include<cstring> 3 char t[1001010],p[10100]; 4 int nex[10100]; 5 int tlen,plen; 6 int ans; 7 void getnex() 8 { 9 int j=0,k=-1; 10 nex[0]=-1; 11 while(j<plen) 12 { 13 if(k==-1||p[j]==p[k]) 14 nex[++j]=++k; 15 else k=nex[k]; 16 } 17 } 18 19 int KMP() 20 { 21 if(tlen==1&&1==plen) 22 { 23 if(t[0]==p[0]) return 1; 24 else return 0; 25 } 26 getnex(); 27 int i=0,j=0; 28 for(;i<tlen;i++) 29 { 30 while(j>0&&t[i]!=p[j]) 31 j=nex[j]; 32 if(t[i]==p[j]) j++; 33 if(j==plen) 34 { 35 ans++; 36 j=nex[j]; 37 } 38 } 39 return ans; 40 } 41 42 int main() 43 { 44 int tt; 45 scanf("%d",&tt); 46 while(tt--) 47 { 48 scanf("%s%s",p,t); 49 ans=0; 50 tlen=strlen(t); 51 plen=strlen(p); 52 printf("%d\n",KMP()); 53 54 } 55 }
hdu2087剪花布条(KMP)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。