Smiling & Weeping
---- 深情是我担不起的重任,情话只是偶然兑现的谎言
题目:Problem - 2087 (hdu.edu.cn)
就是简单的kmp,再加上一个判断是否和上一个重复
现在上模板:
Talk is cheap , show me the code
1 #include<iostream> 2 #include<cstring> 3 #include<cmath> 4 #include<cstdio> 5 #include<algorithm> 6 using namespace std; 7 char str[2010] , pattern[2010]; 8 int Next[2010]; 9 int cnt; 10 void getNext(char *p , int plen){ // 计算Next[1]~Next[plen] 11 Next[0] = 0; Next[1] = 0; 12 for(int i = 1; i < plen; i++){ // 把i的增加看作后缀的逐步扩展 13 int j = Next[i]; // j的后移:j指向前缀阴影w的后一个字符 14 while(j && p[i] != p[j]) // 阴影的后一个字符不相同 15 j = Next[j]; // 更新j 16 if(p[i] == p[j]) Next[i+1] = j+1; 17 else Next[i] = 0; 18 } 19 } 20 void kmp(char *s , char *p){ 21 int last = -1; 22 int slen = strlen(s) , plen = strlen(p); 23 getNext(p , plen); // 预计算Next[]数组 24 int j = 0; 25 for(int i = 0; i < slen; i++){ // 匹配s和p的每个字符 26 while(j && s[i] != p[j]) // 失配了 27 j = Next[j]; // j滑动到Next[j]位置 28 if(s[i] == p[j]) j++; // 当前位置匹配,继续 29 if(j == plen){ // j到了p的末尾,找到了一个匹配 30 if(i-last >= plen){ // 判断新的匹配和上一个匹配是否能分开 31 cnt++; 32 last=i; 33 } 34 } 35 } 36 } 37 int main() 38 { 39 while(~scanf("%s",str)){ 40 if(str[0] == '#') break; 41 scanf("%s",pattern); 42 cnt = 0; 43 kmp(str , pattern); 44 printf("%d\n",cnt); 45 } 46 return 0; 47 }
我是一只决心不再躲闪的鸟
文章到此结束,我们下次再见o(╥﹏╥)o
标签:cnt,int,Next,kmp,plen,include,模板 From: https://www.cnblogs.com/smiling-weeping-zhr/p/17684497.html