南阳5--Binary String Matching(Kmp)

Binary String Matching

时间限制：3000 ms  |  内存限制：65535 KB 难度：3 描述

Given two strings A and B, whose alphabet consist only ‘0’ and ‘1’. Your task is only to tell how many times does A appear as a substring of B? For example, the text string B is ‘1001110110’ while the pattern string A is ‘11’, you should output 3, because the pattern A appeared at the posit

输入

The first line consist only one integer N, indicates N cases follows. In each case, there are two lines, the first line gives the string A, length (A) <= 10, and the second line gives the string B, length (B) <= 1000. And it is guaranteed that B is always longer than A.

输出

For each case, output a single line consist a single integer, tells how many times do B appears as a substring of A.

样例输入

3 11 1001110110 101 110010010010001 1010 110100010101011

样例输出

3 0 3

来源

网络

上传者

naonao

 kmp  裸题；

#include <cstdio> #include <cstring> #include <iostream> using namespace std; char a[15], b[1010]; int p[1010], lena, lenb, ans; void Getp() {int i = 0, j = -1;p[i] = j;while(i != lena){if(j == -1 || a[i] == a[j]){i++, j++;p[i] = j; } elsej = p[j];} } void Kmp() {Getp();int i = 0, j = 0;while(i != lenb){if(j == -1 || b[i] == a[j]) i++, j++;else j = p[j];if(j == lena)ans++; } printf("%d\n", ans); } int main() {int t;scanf("%d", &t);while(t--){ans = 0;scanf("%s%s", a, b);lena = strlen(a);lenb = strlen(b);Kmp();}return 0; }

 

暴力： 竟然也是 0 ms; 

#include <cstdio> #include <cstring> #include <iostream> using namespace std; char a[15], b[1010]; int lena, lenb; int main() {int t;scanf("%d", &t);while(t--){int i, j, sum = 0;scanf("%s %s", a, b);int lena = strlen(a), lenb = strlen(b);for(i = 0; i <= lenb - lena; i++){if(b[i] == a[0]){for(j = 1; j < lena; j++)if(b[i+j] != a[j])break;if(j == lena)sum++;} }printf("%d\n", sum);} return 0; }

 

转载于:https://www.cnblogs.com/soTired/p/4749391.html

总结

以上是生活随笔为你收集整理的南阳5--Binary String Matching(Kmp)的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。