FZU Problem 1926 填空(KMP好题一枚，确实好)

题目：http://acm.fzu.edu.cn/problem.php?pid=1926

#include <iostream>
#include <stdio.h>
#include <string>
#include <string.h>
#include <algorithm>
#include <stdlib.h>
#include <math.h>
#include <vector>
#include <map>
using namespace std;
const int maxn = 1005;
char str[maxn];
string s[maxn],sq[maxn];
int next[maxn];
int len_s,len_sq;
void getnext(string sq[]){
    int i = 0,j = -1;
    next[0] = -1;
    while(i < len_sq){
        if(j == -1 ||sq[i] == sq[j] || sq[i] =="_" ||sq[j] == "_")
            next[++i] = ++j;
        else
            j = next[j];
    }
    //for(int i = 0;i < len_sq;i++)
      //  printf("%d ",next[i]);
}
int kmp(string s[],string sq[]){
    int i = 0,j = 0;
    getnext(sq);
    while(i < len_s){
        while(i < len_s && j < len_sq){
            if(j == -1||s[i] == sq[j]||sq[j] == "_"){
                i++;
                j++;
            }
            else
                j = next[j];
        }
        if(j==len_sq)
            return 1;
    }
    return 0;
    
}
int main(){
    int t,m;
    scanf("%d",&t);
    for(int cas = 1;cas <= t;cas++){
        int num=0;
        while(scanf("%s",str)){
            if(strcmp(str, "@") == 0)
                break;
            s[num++] = string(str);
        }
        len_s = num;
        //for(int i = 0;i < num;i++)
          //  cout<<s[i]<<endl;
        printf("Case %d:\n",cas);
        scanf("%d",&m);
        while(m--){
            num=0;
            while(scanf("%s",str)){
                if(strcmp(str, "@") == 0)
                    break;
                sq[num++] = string(str);
            }
            len_sq = num;
            if(kmp(s,sq))
                printf("YES\n");
            else
                printf("NO\n");
        }
    }
    return 0;
}