ACM简单的字符串匹配,但老是OJ通不过,求大神指点 5C

Description
给出两个字符串S和T,请判断T是否为S的子串。本题请用"简单匹配法"来做。 使用strstr函数,判cheat

Input
第一行是一个整数N,说明有多少个测试用例。

接下来是N个测试用例,每个测试用例占2行:第一行是字符串S,第二行是字符串T,字符串中不含空格。 1 ≤ strlen(S) , strlen( T ) ≤ 10000

Output
对每个测试用例,输出一行结果:是否子串,是则输出"yes" ,否则输出 "no"

Sample Input
2
aabcdd
abc
aaaaaaaaaaaaa
aaaaaab

Sample Output
yes
no

 #include<stdio.h>
#include<string.h>
int main(void){
int t, j, id, g, d;
char s[10005], c[10005], cha;
scanf("%d", &t);
cha=getchar();
for(g=1; g<=t; g++){
gets(s);     gets(c);  

for(j=0,id=0,d=0; j<strlen(s); j++){
if(s[j]!=c[id])     id=0;
if(s[j]==c[id])     id++;
if(id==strlen(c))      {  d++; break;  }
}

if(d!=0)   printf("yes\n");
else       printf("no\n");
}
return 0;
}

5个回答

for(j=0,id=0,d=0; j<strlen(s); j++){
if(s[j]!=c[id]) id=0;
if(s[j]==c[id]) id++;
if(id==strlen(c)) { d++; break; }
}
你这个算法的逻辑有问题呀,你直接先把长串按步长为1,拆分成子串长度大小的几段字符串,
假如
m=len(longstr); n=len(shortstr)
就是把longstr拆分成 m-n+1 个字符串,然后比较一下就行啦~

你看这样可以不?

 #include<stdio.h>
#include<string.h>
int main(void)
{
        int t, j, id, g, d;
        char s[10005], c[10005], cha;
        scanf("%d", &t);
        cha=getchar();
        for(g=1; g<=t; g++){
        gets(s);     gets(c);  

        for(j=0,id=0,d=0; j<strlen(s); j++)//strlen()函数执行多次,每次循环结束执行一次,strlen()时间复杂度为O(n)
        {
            if(s[j]!=c[id])     id=0;
            if(s[j]==c[id])     id++;
            if(id==strlen(c))      {  d++; break;  }//strlen()函数执行多次,每次循环结束执行一次
        }

        if(d!=0)   printf("yes\n");
        else       printf("no\n");
}
        return 0;
}

\这样的代码会超时。。。
\解决方法:

    for(g=1; g<=t; g++)
    {
    gets(s);     gets(c); 
    int l1=strlen(s);
    int l2=strlen(c);
    for(j=0,id=0,d=0; j<l1; j++)
    {
            if(s[j]!=c[id])
                            id=0;
                    if(s[j]==c[id])
                                id++;
                if(id==l2)      
                        {  d++; break;  }
    }

但这样更好

 #include<stdio.h>
#include<string.h>
char s[10010],t[10010];
int n;
int main()
{
    scanf("%d",&n);
    getchar();
    while(n--)
    {
        gets(s);gets(t);
        if(strstr(s,t))printf("yes\n");
        else printf("no\n");
    }
    return 0;
}

使用strstr判作弊。
试试这个:

 #include<string.h>
int main(void)
{
    int t, j, id, g, ls, lc;
    char s[10005], c[10005], cha;
    scanf("%d", &t);
    cha=getchar();
    for(g=1; g<=t; g++)
    {
        gets(s);    gets(c);  
        ls=strlen(s); lc=strlen(c);
        for(j=0,id=0; j<ls; j++)
        {
            if(s[j]!=c[id])
            {
                id=0;
                j--;
            }
            else
            {
                id++;
                if(id==lc) break;
            }
        }

        if(id==lc)  printf("yes\n");
        else       printf("no\n");
    }
    return 0;
}

修改了一个错误。

 #include<stdio.h>
#include<string.h>
int main(void)
{
    int t, j, id, g, ls, lc;
    char s[10005], c[10005], cha;
    scanf("%d", &t);
    cha=getchar();
    for(g=1; g<=t; g++)
    {
        gets(s);    gets(c);  
        ls=strlen(s); lc=strlen(c);
        for(j=0,id=0; j<ls; j++)
        {
            if(s[j]!=c[id])
            {
                if(id>0) j--;
                id=0;
            }
            else
            {
                id++;
                if(id==lc) break;
            }
        }

        if(id==lc)  printf("yes\n");
        else       printf("no\n");
    }
    return 0;
}

字符串匹配?模式匹配这是

Csdn user default icon
上传中...
上传图片
插入图片
抄袭、复制答案,以达到刷声望分或其他目的的行为,在CSDN问答是严格禁止的,一经发现立刻封号。是时候展现真正的技术了!
立即提问