|Hdu 2087|KMP|剪花布条

2019-11-10 20:10:34

字体：大中小

来源：转载

供稿：网友

Hdu传送门 KMP即可。注意不可重叠，用一个last $last$ 记录上一个不重复匹配成功的位置，之后如果匹配成功，记当前位置为i $i$ ，如果i−last>模式串长度 $i-last>模式串长度$ ，即匹配成功，更新last $last$

#include<cstdio> #include<algorithm> #include<cstring> #define ms(i,j) memset(i,j, sizeof i);using namespace std; char s1[1000 + 5], s2[1000 + 5]; int f[1000 + 5];void getFail(){ int len = strlen(s2); f[0] = f[1] = 0; for (int i=1;i<len;i++) { int j = f[i]; while (j && s2[i]!=s2[j]) j = f[j]; f[i+1] = (s2[i]==s2[j]) ? (j+1) : (0); }}int KMP(){ int len = strlen(s1); int l2 = strlen(s2); int last = -1; int ret = 0; int j = 0; for (int i=0;i<len;i++) { while (j && s1[i]!=s2[j]) j = f[j]; if (s1[i]==s2[j]) j++; if (j==l2) { if (i-last>=l2) { ret++; last = i; } } } return ret;}int main() { while (scanf("%s", s1)&&s1[0]!='#') { scanf("%s", s2); getFail(); PRintf("%d/n", KMP()); } return 0; }

上一篇：28.日志路由组件

下一篇：表的内连接、外连接（左连接与右连接）