Binary String Matching

http://acm.nyist.net/JudgeOnline/problem.php?pid=5

描述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

 1 #include<stdio.h>
 2 #include<string.h>
 3 int main()
 4 {
 5     int n;
 6     scanf("%d
",&n);
 7     while(n--)
 8     {
 9     char a[15],b[1010];
10     int la,lb,p,i,j,count=0;
11     scanf("%s",a);
12     scanf("%s",b);
13     la=strlen(a);
14     lb=strlen(b);
15     for(i=0;i<lb;i++)
16     {
17         p=1;
18         if(a[0]==b[i])
19         {
20             for(j=i;j<i+la;j++)
21             {
22                 if(a[j-i]!=b[j])
23                 {
24                     p=0;
25                     break;
26                 }
27     
28             }
29             if(p==1)
30             count++;
31         }
32         
33     }
34      printf("%d
",count);
35     }
36 return 0;
37 }

View Code