3782 - 【START】2015暑期训练——Binary String Matching
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
Input
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.
Output
For each case, output a single line consist a single integer, tells how many times do B appears as a substring of A.
Examples
Input
3 11 1001110110 101 110010010010001 1010 110100010101011
Output
3 0 3
Solution C
#include<stdio.h> #include<string.h> int main() { int n,count; char *p=NULL; char A[11],B[1001]; scanf("%d",&n); getchar(); for(int i=0;i<n;i++) { count=0; gets(A); gets(B); int a=strlen(A); int b=strlen(B); int j=0; if(b-a>0) { for(p=B;j<=b-a;p++,j++) { if(*p==A[0]) { int k; for(k=1;k<a;k++) { if(*(p+k)==A[k]) continue; else break; } if(k==a) count++; } } } printf("%d\n",count); } return 0; }
Solution C++
#include<iostream> #include<string> #include<cstdio> using namespace std; int main() { //freopen("1.txt","r",stdin); //freopen("2.txt","w",stdout); int n; cin >> n; string a,b; int len_a; int dl; // a 和 b 长度查 int cnt; // 计数 int i,j,k; while(n--) { cin >> a >> b; cnt = 0; len_a = a.length(); dl = b.length()-a.length(); for(i = 0; i <= dl; i++) { // 应该是等于 k = i; for(j = 0; j < len_a && a[j]==b[k]; j++, k++); if(j == len_a) { cnt++; } } cout << cnt << endl; } return 0; }