HDU - 2087 剪花布条——kmp

HDU - 2087 剪花布条——kmp

模板题

#include #include #include #include using namespace std;const int maxn = 1000 + 10;char s[maxn], p[maxn];int lens, lenp, Next[maxn];void makeNext() { int pos = 0, len = 0; Next[pos] = len; for (pos = 1; pos < lenp; pos++) { while (len && p[pos] != p[len]) len = Next[len - 1]; if (p[pos] == p[len]) len++; Next[pos] = len; }}int kmp() { int ans = 0; makeNext(); for (int i = 0, j = 0; i < lens; i++) { while (j && s[i] != p[j]) j = Next[j - 1]; if (s[i] == p[j]) j++; if (j == lenp) { ans++; j = 0; } } return ans;}int main() { while (~scanf("%s", s) && s[0] != '#') { scanf("%s", p); lens = strlen(s), lenp = strlen(p); printf("%d\n", kmp()); } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。