题目描述

给定一个短字符串（不含空格），再给定若干字符串，在这些字符串中删除所含有的短字符串。

输入

输入只有1组数据。
输入一个短字符串（不含空格），再输入若干字符串直到文件结束为止。

输出

删除输入的短字符串(不区分大小写)并去掉空格,输出。

样例输入

in
#include 
int main()
{

printf(" Hi ");
}

样例输出

#clude
tma()
{

prtf("Hi");
}

提示

注:将字符串中的In、IN、iN、in删除。

代码

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include <ctype.h>
#define MATCH 100
#define MAX 1000
  
int fail[MATCH];
  
void compute_prefix(char *p)
{
    int i, m, k;
  
    m = strlen(p);
    k = 0;
  
    for (i = 2; i <= m; i ++) {
        while (k > 0 && p[k] != p[i - 1]) {
            k = fail[k - 1];
        }
  
        if (p[k] == p[i - 1]) {
            k = k + 1;
        }
  
        fail[i - 1] = k;
    }
}
  
  
int kmp_match(char *p, char *s, char *flag)
{
    int i, m, n, k, j;
  
    // 初始化匹配数组
    memset(flag, -1, sizeof(flag));
  
    // 初始化fail数组
    compute_prefix(p);
  
    m = strlen(p);
    n = strlen(s);
    k = j = 0;
  
    for (i = 0; i < n; i ++) {
        while (k > 0 && p[k] != s[i]) {
            k = fail[k - 1];
        }
  
        if (p[k] == s[i]) {
            k = k + 1;
        }
  
        if (k == m) {
            flag[j] = i - m + 1;
            j ++;
            k = fail[k - 1];
        }
    }
  
    return j;
}
  
  
int main()
{
    char p[MATCH], t[MAX][MAX], s[MAX][MAX], flag[MAX];
    int i, m, num, index, j, k, sign;
  
    // 处理模式串
    scanf("%s", p);
    getchar();
    m = strlen(p);
    for (i = 0; i < m; i ++) {
        if (p[i] >= 'A' && p[i] <= 'Z') {
            p[i] = tolower(p[i]);
        }
    }
  
    // 接收文本串
    for (index = 0; gets(t[index]); index ++) {
        if (strcmp(t[index], "}") == 0) {
            break;
        }
    }
  
    // 复制文本串转小写
    for (i = 0; i <= index; i ++) {
        for (j = 0; j < strlen(t[i]); j ++) {
            if (t[i][j] >= 'A' && t[i][j] <= 'Z') {
                s[i][j] = tolower(t[i][j]);
            }else {
                s[i][j] = t[i][j];
            }
        }
    }
  
    // 按行kmp匹配
    for (i = 0; i <= index; i ++) {  
        // 判断是否是匹配点
        num = kmp_match(p, s[i], flag);
        for (j = 0; j < strlen(t[i]);) {
            for (k = 0, sign = 1; k < num; k ++) {
                if (flag[k] == j) {
                    sign = 0;
                    break;
                }
            }
            if (sign) {
                if (t[i][j] != ' ') {
                    printf("%c", t[i][j]);
                }
                j ++;
            }else {
                j += m;
            }
        }
        printf("\n");
    }
    printf("\n");
  
    return 0;
}