列表

详情

BD5. 字符串匹配

描述

牛牛有两个字符串A和B,其中A串是一个01串,B串中除了可能有0和1,还可能有'?',B中的'?'可以确定为0或者1。 寻找一个字符串T是否在字符串S中出现的过程,称为字符串匹配。牛牛现在考虑所有可能的字符串B,有多少种可以在字符串A中完成匹配。

例如:A = "00010001", B = "??"
字符串B可能的字符串是"00","01","10","11",只有"11"没有出现在字符串A中,所以输出3

输入描述

输入包括两行,第一行一个字符串A,字符串A长度length(1 ≤ length ≤ 50),A中每个字符都是'0'或者'1'。 第二行一个字符串B,字符串B长度length(1 ≤ length ≤ 50),B中的字符包括'0','1'和'?'。

输出描述

输出一个整数,表示能完成匹配的字符串种数。

示例1

输入: 

00010001
??

输出: 

3

原站题解

C 解法, 执行用时: 2ms, 内存消耗: 368KB, 提交时间: 2020-09-09 

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int str_cmp(char *a1,char *a2,int len){
    
    int i;
    int flag = 1;
    if(a1 ==NULL || a2 == NULL ||len < 0)
    {
        printf("params error.\n");
        exit(-1);
    }
    for(i = 0; i < len ;i++)
    {
        if(a1[i]!=a2[i] && a2[i]!='?')
        {
            flag = 0;
            break;
        }
    }
    return flag;
}
int main(){
    int i,j,counter =0;
    int len_main = 0,ind = 0;
    int len_sub= 0,count = 0,res = 0;
    char main_str[50];
    char sub_str[50];
    char str_tmp[50];
    char save[50][50];
    scanf("%s", main_str);
    scanf("%s", sub_str);
    len_main = strlen(main_str);
    len_sub = strlen(sub_str);
  
    ind = 0;
    if(len_sub > len_main)
    {
        return 0;
    }
    else
    {
        while(ind <= len_main - len_sub)
        {
            for(i = ind ;i < ind+len_sub ;i++)
            {
                str_tmp[i-ind] =main_str[i]; 
            }
			
			str_tmp[len_sub] ='\0';
			ind++;
            res =  str_cmp(str_tmp,sub_str,len_sub);
            if(res != 1) continue;
            for(i = 0; i< 50 ;i++)
            {
                if(strcmp(str_tmp,save[i])==0)
                {
                    break;
                }
            }
            if(i ==50)
            {
                count ++;
                strcpy(save[counter], str_tmp);
                counter++;
            }
            
        }
    }
    printf("%d \n",count);

    return 0;
}

C 解法, 执行用时: 2ms, 内存消耗: 368KB, 提交时间: 2020-06-07 

#include<stdio.h>
#include<string.h>
#define MAX 55
char str[55][55];
int ans = 0;
int analyze(char str[][MAX],char * tmp,int anss)//比较两个字符串 字符串  要比较的字符 数量
{
    int i;
    for(i=0;i<anss;i++){
        if(strcmp(str[i],tmp)==0)
            return 0;
    }
    return 1;
}
int get_cnt(char sr[][MAX], char * B,int N)
{
    int i,j,cnt,flag;
    cnt = 0;
    for(i=0;i<ans;i++){
        flag = 1;
        for(j=0;j<N;j++)
            if(str[i][j]!=B[j] && B[j]!='?')
            {flag = 0;break;}
        if(flag == 1)
            cnt++;
    }
    return cnt;
}
int main()
{
    char A[MAX],B[MAX];
    int lena;
    int lenb;
    int i;
    int j=0;
    int l;
    int r;
    char tmp[MAX];
    int cnt;
    scanf("%s", A);
    scanf("%s", B);
    lena = strlen(A);
    lenb = strlen(B);
    l = 0;
    r = lenb;
    while(r<=lena)
    {
       j=0;
      for(i=l;i<=r-1;i++)
       {
         tmp[j++]=A[i];
       }
       if(analyze(str,tmp,ans))
        strcpy(str[ans++],tmp);
       l++;
       r++;
    }
       
    cnt = get_cnt(str,B,lenb);//这里
    printf("%d", cnt);
    return 0;
}

C 解法, 执行用时: 2ms, 内存消耗: 372KB, 提交时间: 2020-11-14 

#include <stdio.h>
#include <string.h>
int compare(char* A, char* B, int b_len){
    int i;
    for(i = 0; i < b_len; i++){
        if(B[i] == '?')continue;
        if(B[i] != A[i])return 0;
    }
    return 1;
}

int main(){
    char* A = (char*)malloc(51*sizeof(char));
    char* B = (char*)malloc(51*sizeof(char));
    while(scanf("%s", A) != EOF){
        scanf("%s", B);
        int a_len = strlen(A);
        int b_len = strlen(B);
        int n = 0;
        int flag = 0;
        char* temp = (char*)malloc(50*sizeof(char));
        char** store = (char**)malloc(50*sizeof(char*));
        //char store[50][51];
        for(int i = 0; i <= a_len - b_len; i++){
            if(compare((char*)(A + i), B, b_len) == 1){
                flag = 0;
                strcpy(temp, (char *)(A+i));
                temp[b_len] = '\0';
                for(int j = 0; j < n; j++){
                    if(strcmp(temp, store[j]) == 0){
                        flag = 1;
                        break;
                    }
                }
                if(flag == 1)continue;
                store[n] = (char *)malloc(51*sizeof(char));
                strcpy(store[n], temp);
                n++;
            }
        }
        printf("%d\n", n);
        for(int i = 0; i < n; i++){
            free(store[i]);
        }
        free(store);
    }
}

C 解法, 执行用时: 2ms, 内存消耗: 372KB, 提交时间: 2019-07-22 

#include<stdio.h>
#include<string.h>
#define MAX 55
char str[55][55];
int ans = 0;
int analyze(char str[][MAX],char * tmp,int anss)//比较两个字符串 字符串  要比较的字符 数量
{
    int i;
    for(i=0;i<anss;i++){
        if(strcmp(str[i],tmp)==0)
            return 0;
    }
    return 1;
}
int get_cnt(char sr[][MAX], char * B,int N)
{
    int i,j,cnt,flag;
    cnt = 0;
    for(i=0;i<ans;i++){
        flag = 1;
        for(j=0;j<N;j++)
            if(str[i][j]!=B[j] && B[j]!='?')
            {flag = 0;break;}
        if(flag == 1)
            cnt++;
    }
    return cnt;
}
int main()
{
    char A[MAX],B[MAX];
    int lena;
    int lenb;
    int i;
    int j=0;
    int l;
    int r;
    char tmp[MAX];
    int cnt;
    scanf("%s", A);
    scanf("%s", B);
    lena = strlen(A);
    lenb = strlen(B);
    l = 0;
    r = lenb;
    while(r<=lena)
    {
       j=0;
      for(i=l;i<=r-1;i++)
       {
         tmp[j++]=A[i];
       }
       if(analyze(str,tmp,ans))
        strcpy(str[ans++],tmp);
       l++;
       r++;
    }
      
    cnt = get_cnt(str,B,lenb);//这里
    printf("%d", cnt);
    return 0;
}

C 解法, 执行用时: 2ms, 内存消耗: 372KB, 提交时间: 2019-05-26 

#include<stdio.h>
#include<string.h>
#define MAX 55
  
char str[55][55];
int ans = 0;
int analyze(char str[][MAX],char * tmp,int anss)
{
    int i;
    for(i=0;i<anss;i++){
        if(strcmp(str[i],tmp)==0)
            return 0;
    }
    return 1;
}
   
int get_cnt(char sr[][MAX], char * B,int N)
{
    int i,j,cnt,flag;
    cnt = 0;
    for(i=0;i<ans;i++){
        flag = 1;
        for(j=0;j<N;j++)
            if(str[i][j]!=B[j] && B[j]!='?')
            {flag = 0;break;}
        if(flag == 1)
            cnt++;
    }
    return cnt;
}
int main()
{
    char A[MAX],B[MAX];
    
    int lena;
    int lenb;
    int i;
    int j;
    int l;
    int r;
    char tmp[MAX];
int cnt;
 scanf("%s", A);
    scanf("%s", B);
    lena = strlen(A);
    lenb = strlen(B);
    l = 0;r = lenb;
 
    while(r<=lena){
    for(i=l,j=0;i<=r-1;i++,j++)
        tmp[j]=A[i];
    if(analyze(str,tmp,ans))
        strcpy(str[ans++],tmp);
    l++;r++;
    }
     
    cnt = get_cnt(str,B,lenb);//这里
    printf("%d", cnt);
    return 0;
}

上一题

© 2024 nowcoder.com