Binary String Matching——个人c++解

傷城~ 2022-06-16 03:59 202阅读 0赞

## 描述 ##

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

## 样例输出 ##

[点击打开题目链接][Link 1]：http://acm.nyist.net/JudgeOnline/problem.php?pid=5

## 解题思路 ##

第一个字符串a在第二个字符串b中出现的次数，循环判断a\[0\]和b的依次往后的一样的字符，如果一样，调用函数继续判断后面的字符是否相同。这样的话，可以将b的每一个字符加以判断。代码如下：

#include <bits/stdc++.h>
    using namespace std;
    bool xd(char *a,char *b,int &w,int &j)
    {
        int i;
        for(i=0;i<w;i++)
        {
            if(*(a+i)!=*(b+j+i))break;
        }
        if(i==w)return true;
        else return false;
    
    }
    int main()
    {
        int n,i,q,w,u;
        char a[11],b[1001];
        cin>>n;
        while(n--)
        {
            u=0;
            cin>>a>>b;
            w=strlen(a);
            q=strlen(b);
            for(i=0;i<q;i++)
            {
                if(a[0]==b[i])//循环判断a[0]和b的依次往后的一样的字符
                {
                    if(xd(a,b,w,i)==true)//相同的话，xd函数继续判断以后字符是否都相同
                        u=u+1;//每次相同次数加一
                }
            }
            cout<<u<<endl;
        }
        return 0;
    }

[Link 1]: http://acm.nyist.net/JudgeOnline/problem.php?pid=5