Description 给定一个源串s和n个子串stri。判断stri是否是s的子串。 Input

Question

Description 给定一个源串s和n个子串stri。判断stri是否是s的子串。 Input 输入数据有多组，对于每组测试数据 第一行源串S（S长度小于100000），第二行一个整数n， 表示下面有n个查询，每行一个字符串str。 Output 若str是S的子串，输出 yes 否则输出 no Sample Input： acmicpczjnuduzongfei 3 icpc du liu Sample Output： yes yes no 我的代码： #include #include int next[100000]; void get_next(char *T,int next[]){ int i=0;next[0]=-1;int j=-1; while(istrlen(T)-1)return i-strlen(T)+1; else return -1; } int main(){ char S[100000],T[100000]; int n,i; while(scanf("%s",S)!=EOF){ scanf("%d",&n); for(i=1;i<=n;i++){ scanf("%s",T); get_next(T,next); if(Index_KMP(S,T)!=-1)printf("yes\n"); else printf("no\n"); } } } 我的问题：我觉得我的代码没有问题，但是就是答案错误，望大佬帮帮忙！

Answer 1

 

#include<stdio.h>

#include<string.h>

# define MAXSTRLEN 100000

typedef unsigned char SString [MAXSTRLEN+1];

 

 

int Nextval[100000];

 

void get_Nextval(SString T,int Nextval[ ])

{

 int i=1,j=0;

    Nextval[1]=0;

    while(i<T[0])

    {

     if(j==0||T[i]==T[j]){

      ++i;++j;

      if(T[i]!=T[j])Nextval[i]=j;

      else Nextval[i]=Nextval[j];

     }//if

     else j=Nextval[j];

    }//while

}//get_nextval

 

int KMP(SString S,SString T)

{

 int i=1,j=1;

 while(i<=S[0]&&j<=T[0])

       {

        if(j==0||S[i]==T[j]){++i;++j;}

        else j=Nextval[j]; //回溯j指针 

       }

       if(j>T[0]) return i-T[0];

    else return 0; 

}

 

 

void init(SString T,char t[ ])

{

 int x,i; 

 x=strlen(t);

 for(i=1;i<=x;i++)

 {

  T[i]=t[i-1];

 }

 T[0]=x;

}

 

 

int main()

{

 SString T,S;

 char t[100000],s[100000];

 int n,x,y,i,j,m;

 while(scanf("%s",s)!=EOF){

  

 getchar();

 init(S,s);//初始化T数组 

 

    scanf("%d",&n);

    

    for(m=0;m<n;m++)

    { scanf("%s",t);getchar();

       init(T,t); //初始化T数组  

       

       get_Nextval(T,Nextval);//获取nextval数组 

       

       j=KMP(S,T); 

       

       if(j) printf("yes\n");

       else printf("no\n");

    }//for

    }//while

    return 0;    

}