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; } else j = 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 ", 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 ", sum); } return 0; }