南阳OJ----Binary String Matching

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

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
typedef struct node
{
  char a;
  struct node *next;
}Node;
int i;
bool flag=true;
int main( void )
{
    Node *head,*p1,*p2;
    int t,n,count;
    scanf("%d",&t);
    getchar();
    while(t--)
    {
        head=NULL;
        count=n=0;
        p1=p2=( Node * )malloc( sizeof(Node) );
        char str[10]={'\0'};
        gets(str);
        //getchar();
        while(p1->a=getchar(),p1->a!='\n')
        {
            if(n++==0)
                      head=p1;
            else 
                 p2->next=p1;
                 p2=p1;
            p1=(Node*)malloc(sizeof(Node));
        }
        p2->next=NULL;
          p1=head;
    /*      while(p1!=NULL)
          {
              putchar(p1->a);
              p1=p1->next;
          }
          puts("");
    */
         while(p1!=NULL)
         {
         
              while(p1!=NULL&&p1->a!=*str)   //找到第一个位置
                 {
                   p1=p1->next;
                 }
              if(p1!=NULL)                //防止万一没有找到
              {
                  p2=p1->next;

                for( ::i=0; str[i]!='\0'; i++ )
                {
                  if(str[i]==p1->a)
                  {
                      p1=p1->next;
                  }
                  else 
                  {
                      ::flag=false;
                           p1=p2;
                             break;
                  }
                  
                  if((p1==NULL&&str[i+1]!='\0'))
                      {
                         ::flag=false ;
                          break;
                      }
                }
                    
                 if(::flag)
                 {
                          p1=p2 ;
                          count++;
                 }
                else 
                    ::flag=true;
              }
            }

         free(head);
         printf("%d\n",count);
        
         }
    return 0;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

ml

659 篇文章64 人订阅

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏程序员互动联盟

【编程入门】C语言堆栈入门——堆和栈的区别

在计算机领域,堆栈是一个不容忽视的概念,我们编写的C语言程序基本上都要用到。但对于很多的初学着来说,堆栈是一个很模糊的概念。堆栈:一种数据结构、一个在程序运行时...

62560
来自专栏程序员互动联盟

老码农拍着脑袋总结的法子

1.扎实的基础。数据结构、离散数学、编译原理,这些是所有计算机科学的基础,如果不掌握他们,很难写出高水平的程序。据我的观察,学计算机专业的人比学其他专业的人更能...

395150
来自专栏程序员互动联盟

【高级编程】C++中vector使用详解

1. 在C++中的详细说明 vector是C++标准模板库中的部分内容,它是一个多功能的,能够操作多种数据结构和算法的模板类和函数库。 vector之所以被认为...

445110
来自专栏程序员互动联盟

一个程序员的奋斗历程

也许,你还为你的未来感到迷茫,也许,你还对程序员的历程感到神奇.就让我们来看看这位程序员的奋斗历程好了. 这些日子我一直在写一个实时操作系统内核,已有小成了,...

47580
来自专栏机器学习AI算法工程

知乎观点收集:关于机器学习和数据挖掘找工作

甲:数据挖掘 很多地方招聘还是挺喜欢这样专业的,但是前提是你得过笔试关。 为了笔试,学习C和数据结构 数据挖掘的时候学习算法和推理机制等,看看数据分析,神经网络...

51970
来自专栏美团技术团队

HDFS NameNode内存详解

前言 《HDFS NameNode内存全景》中,我们从NameNode内部数据结构的视角,对它的内存全景及几个关键数据结构进行了简单解读,并结合实际场景介绍了N...

48160
来自专栏Netkiller

征信区块链解决方案探索(Hyperledger)

中国广东省深圳市龙华新区民治街道溪山美地 518131 +86 13113668890 <netkiller@msn.com>

2.1K270
来自专栏腾讯研究院的专栏

大数据时代商业银行的策略

  尽管大数据对商业银行的影响目前而言还比较小,但从发展趋势看,要充分认识大数据的颠覆性影响。各银行必须未雨绸缪,早做布局,从管理体系建设、具体运用模式方面不...

435130
来自专栏JadePeng的技术博客

从Trie树到双数组Trie树

Trie树 原理 又称单词查找树,Trie树,是一种树形结构,是一种哈希树的变种。它的优点是:利用字符串的公共前缀来减少查询时间,最大限度地减少无谓的字符串比较...

1.1K60
来自专栏机器学习AI算法工程

KMeans聚类算法思想与可视化

1.聚类分析 1.0 概念 聚类分析简称聚类(clustering),是一个把数据集划分成子集的过程,每一个子集是一个簇(cluster),使得簇中的样本彼此...

1.3K60

扫码关注云+社区

领取腾讯云代金券

年度创作总结 领取年终奖励