题解第四章字符串| KMP方法#单词替换#

法1:

复习一下KMP算法

通过KMP算法,可以轻松求出匹配的字符串的位置

可以参考如下链接:https://blog.nowcoder.net/n/82f6d123408c4d5db19cda68501d8d85

本题作了一些改变:必须要是整个的单词进行匹配才能替换,单词的前后,必须有空格

如果目标单词是大单词的一部分时,则不能够替换

再通过标记好的位置输出

另外

//采用KMP模式串匹配算法,能够更加通用得做出本题
#include <stdio.h>
#define MAX 150

//用来求KMP算法中必须的的nextval模式匹配数组
void getNextval(const char Target[], int nextval[], int Size)
{
    int i = 0, j = -1;
    int next[Size];
    next[0] = -1;
    nextval[0] = -1;
    while (i < Size)
    {
        if (j == -1 || Target[i] == Target[j])
        {
            next[++i] = ++j;
            if (Target[i] == Target[next[i]])
                nextval[i] = nextval[next[i]];
            else
                nextval[i] = next[i];
        }
        else
            j = next[j];
    }
}

//采用KMP算法
//将各次匹配成功的位置全部计入数组P中
//匹配成功后附带检验标准:
// 1若位置非零,且前一位非空格,则不算数
// 2末尾+1必须也是空格,否则不算数
//最后以-1为数组的结尾标志
void KMP_Multi(const char CArr[], const char Target[], int P[])
{
    //生成并求出目标串的nextval数组
    int Size = strlen(Target);
    int nextval[MAX] = {0};
    getNextval(Target, nextval, Size);

    int L_CArr = strlen(CArr), L_Target = strlen(Target);

    int i = 0, j = 0, R = 0;

    while (1)
    {
        while (i < L_CArr && j < L_Target)
        {
            if (j == -1 || CArr[i] == Target[j])
                i++, j++;
            else
                j = nextval[j];
        }
        if (j == L_Target)
        {
            int tmp = i - j;
            // ver1以下是从后续开始,不找包含重复的部分
            // /*
            i = i - j + L_Target;
            j = 0;
            // */
            // ver2以下是找出所有的重复部分
            /*
            i = i - j + 1;
            j = 0;
            */
            
            //以下给出了形成单词的前提要求
            if (tmp == 0 || CArr[tmp - 1] == ' ')
                if (tmp + L_Target == L_CArr || CArr[tmp + L_Target] == ' ')
                    P[R++] = tmp;
        }
        else
        {
            P[R] = -1;
            break;
        }
    }
}

int main()
{
    //下面先输入了全部数据
    char CArr[MAX] = {0}, Target[MAX] = {0}, Rep[MAX] = {0};
    //正常得获得主字符串
    fgets(CArr, MAX, stdin);
    CArr[strlen(CArr) - 1] = '\0';
    fgets(Target, MAX, stdin);
    Target[strlen(Target) - 1] = '\0';
    fgets(Rep, MAX, stdin);
    Rep[strlen(Rep) - 1] = '\0';
    //记录三个数组的长度
    int L_CArr = strlen(CArr),
        L_Target = strlen(Target),
        L_Rep = strlen(Rep);

    //采用KMP算法求出目标串各次匹配成功的位置
    //并且存入一个记录位置的数组中
    int P[MAX] = {0};
    KMP_Multi(CArr, Target, P);

    //通过记录下的断点输出结果
    if (P[0] != -1)
    {
        int i = 0, j = 0;
        for (j = 0; j < P[0]; j++)
            putchar(CArr[j]);
        while (P[++i] != -1)
        {
            printf("%s", Rep);
            for (j = P[i - 1] + L_Target; j < P[i]; j++)
                putchar(CArr[j]);
        }
        printf("%s", Rep);
        for (j = P[i - 1] + L_Target; j < L_CArr; j++)
            putchar(CArr[j]);
        putchar('\n');
    }
    else
        printf("%s\n", CArr);
    return 0;
}

将上面输出方法替换能更快得出结果

    //通过记录下的断点输出结果
    if (P[0] != -1)
    {
        int i = 0, j = 0;
        printf("%.*s",P[0],CArr); 
        while (P[++i] != -1)
        {
            printf("%s", Rep);
            printf("%.*s",P[i]-P[i-1]-L_Target,CArr+P[i-1]+L_Target); 
        }
        printf("%s", Rep);
        printf("%.*s",L_CArr-P[i-1]-L_Target,CArr+P[i-1]+L_Target); 
        putchar('\n');
    }
    else
        printf("%s\n", CArr);
    return 0;

法2:

直接替换,

逐个取出单词放到暂存数组,并进行比较和输出

#include <stdio.h>
#include <string.h>
#define MAX 150
int main()
{
    char s[MAX], a[MAX], b[MAX], tmp[MAX];
    while (fgets(s, MAX, stdin))
    {
        s[strlen(s) - 1] = '\0';
        fgets(a, MAX, stdin);
        a[strlen(a) - 1] = '\0';
        fgets(b, MAX, stdin);
        b[strlen(b) - 1] = '\0';

        for (int i = 0; i < strlen(s); i++)
        {
            int k = 0;
            while (s[i] != ' ' && s[i] != '\0')
                tmp[k++] = s[i++]; //当非空时,逐步将s字符串读入tmp
            tmp[k] = '\0';         //将读入的tmp与要替换的单词作比较
            if (strcmp(tmp, a) == 0)
                printf("%s ", b); //如果某一单词不同,输入替换的b
            else
                printf("%s ", tmp);
        }
    }
}

题解 第四章字符串| KMP方法#单词替换#

题解第四章字符串| KMP方法#单词替换#