Home ProblemSet Standing Status Statistics
Problem M: 二进制串匹配
Time Limit: 3 Sec Memory Limit: 128 MB
Submit: 786 Solved: 527
[Submit][Status]
Description
给定两个二进制串A和B,只有“0”和“1”组成。现在的任务是求出串A在串B中出现多少次?
例如,串B是“1001110110”而串A为“11”,你应该输出3。
Input
第一行为一个整数n,表示下面有n组样例。在每一组样例中有两行,第一行给出了二进制串A,A长度不超过10,第二行给出了二进制串B,B的长度不超过1000。并且保证B总是长于A。
#include
#include
int main()
{
int n;
char s[1010],m[1010],t[1010];
scanf("%d",&n);
int i,j,k,x=0;
int flag=0;
for(i=0;iscanf("%s",s);
scanf("%s",m);
for(j=0;j<strlen(m);j++)
{
if(s[0]==m[j])
{
for(k=0;k<strlen(s);k++)
{
t[k]=m[k+j];
}
}
}
if(strcmp(s,t)==0)
{
flag++;
}
printf("%d\n",flag);
}
}
串匹配问题,输出结果不对。
在代码中,对于每一组测试数据,都只初始化了一个计数变量 flag,但没有在处理下一组测试数据时将其重置为 0。这会导致后面的测试数据受到之前测试数据的影响,从而导致计数错误。应该在处理每组测试数据前将 flag 变量重置为 0。
此外,在匹配字符串时,对于每一个匹配到的起始位置 j,只在 s[0] == m[j] 时开始了循环,但这会导致可能存在多个匹配的起始位置被忽略。正确的做法是应该在每一个匹配到的起始位置 j 开始一个循环,依次比较后面的字符是否也匹配,如果有不匹配的字符,则跳出循环;如果一直匹配到 s 的结尾,说明这是一个匹配,累加 flag。
以下是修改后的代码:
#include<stdio.h>
#include<string.h>
int main()
{
int n;
char s[1010],m[1010],t[1010];
scanf("%d",&n);
int i,j,k,x=0;
for(i=0;i<n;i++)
{
scanf("%s",s);
scanf("%s",m);
int flag=0;
for(j=0;j<strlen(m);j++)
{
if(s[0]==m[j])
{
for(k=0;k<strlen(s);k++)
{
if(s[k]!=m[j+k]) break;
}
if(k==strlen(s)) flag++;
}
}
printf("%d\n",flag);
}
return 0;
}
该回答引用ChatGPT
#include<stdio.h>
#include<string.h>
int main()
{
int n;
char s[1010], m[1010], t[1010];
scanf("%d", &n);
int i, j, k, flag;
for (i = 0; i < n; i++)
{
scanf("%s", s);
scanf("%s", m);
flag = 0;
for (j = 0; j <= strlen(m) - strlen(s); j++) // 遍历所有可能的子串
{
for (k = 0; k < strlen(s); k++)
{
t[k] = m[k + j];
}
if (strcmp(s, t) == 0)
{
flag++;
}
}
printf("%d\n", flag);
}
return 0;
}