文字列の検索削除

前言
昨晩kmpのアルゴリズムを理解したばかりで、今日はもちろん問題を見つけて手を練習したいと思って、kmpを使うのはかえって面倒だと感じて、しかし学んだ知識に対して強固にするようにしましょう
タイトル

    ：
        （    ），        ，                 。
  ：
    1   。
        （    ），                。
  ：
         (      )     ,  。
    ：
in
#include 
int main()
{

printf(" Hi ");
}
    ：
#clude
tma()
{

prtf("Hi");
}
  ：
 :      In、IN、iN、in  。

構想

まず、処理モード列とテキスト列

kmpアルゴリズムを用いてマッチング位置を探し出し、印刷出力時にマッチング位置を省略すれば

である.
ACコード

#include 
#include 
#include 
 
#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("
");
    }
    printf("
");
 
    return 0;
}
/**************************************************************
    Problem: 1168
    User: wangzhengyi
    Language: C
    Result: Accepted
    Time:0 ms
    Memory:2796 kb
****************************************************************/