问题描述

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

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("yesn");
else       printf("non");
}
return 0;
}

解决方案

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("yesn");
        else       printf("non");
}
        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("yesn");
        else printf("non");
    }
    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("yesn");
        else       printf("non");
    }
    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("yesn");
        else       printf("non");
    }
    return 0;
}

解决方案五：

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