DS串应用--串替换

128 阅读 0 评论 85 点赞

我是靠谱客的博主激情小蘑菇，这篇文章主要介绍DS串应用--串替换，现在分享给大家，希望可以做个参考。

题目描述

思路分析

AC代码

题目描述

给出主串、模式串、替换串，用KMP算法找出模式串在主串的位置，然后用替换串的字符替换掉模式串

本题只考虑一处替换的情况，如果你想做的完美一些，能够实现多处替换那

可能需要考虑模式串和替换串长度不一致的情况

输入

第一个输入t，表示有t个实例

第二行输入第1个实例的主串，第三行输入第1个实例的模式串，第四行输入第1个实例的替换串

以此类推

输出

第一行输出第1个实例的主串

第二行输出第1个实例的主串替换后结果，如果没有发生替换就输出主串原来的内容。

以此类推

输入样例1

3
aabbccdd
bb
ff
aaabbbccc
ddd
eee
abcdef
abc
ccccc

输出样例1

aabbccdd
aaffccdd
aaabbbccc
aaabbbccc
abcdef
cccccdef

思路分析

题目说了两个点，一个是必用KMP，一个是只替换一处。

KMP关键求next值，求解next值的过程就是KMP。

next值似乎有两种模样，一种是从下标0开始的，next起始值为-1和0，另一种是从下标1开始的，next的起始值为0和1。

我课上学的是下标从1开始的，next【0】存的是子串的长度，下一个next值需要根据前一个next值来确定，首先判断当前字符的前面所组成的字符串的前后缀（前一个字符和第一个字符）是否是相同的字符，如果相同，那么当前字符的next值为前一个next值+1，如果不同，继续比较前一个字符和前一个next值所对应的字符是否相同，如果都不相同，那么next值为1。

利用KMP返回的子串的位置，使用replace函数，完事。

AC代码

复制代码

#include <bits/stdc++.h>

using namespace std;

int FindNext(string &str, int *next) {
    next[0] = str.size();
    next[1] = 0;
    int i = 2, j = 0;
    while (i <= next[0]) {
        if (j == 0 || str[i - 2] == str[j-1]) {
            next[i] = j + 1;
            i++;
            j = next[i - 1];
        } else j = next[j];
        
    }
	return 0;
}

int KMP(string &master, string &son, int *next) {
    int i = 1, j = 1;
    while (i<=master.size() &&j<=son.size()) {
        if (j == 0 || master[i - 1] == son[j - 1]) {
            ++i;
            ++j;
        } else j = next[j];
    }
    if (j > next[0])return i - next[0]-1;
    return -1;
}

int main() {
    int t;
    cin >> t;
    while (t--) {
        string son, master,step_son;
        cin >> master >> son>>step_son;
        int next[son.size() + 1];
        FindNext(son, next);
        cout<<master << endl;
        if(KMP(master, son, next)!=-1)
        master.replace(KMP(master, son, next),son.size(),step_son) ;
		cout<<master<< endl;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include <bits/stdc++.h>

using namespace std;

int FindNext(string &str, int *next) {
    next[0] = str.size();
    next[1] = 0;
    int i = 2, j = 0;
    while (i <= next[0]) {
        if (j == 0 || str[i - 2] == str[j-1]) {
            next[i] = j + 1;
            i++;
            j = next[i - 1];
        } else j = next[j];
        
    }
	return 0;
}

int KMP(string &master, string &son, int *next) {
    int i = 1, j = 1;
    while (i<=master.size() &&j<=son.size()) {
        if (j == 0 || master[i - 1] == son[j - 1]) {
            ++i;
            ++j;
        } else j = next[j];
    }
    if (j > next[0])return i - next[0]-1;
    return -1;
}

int main() {
    int t;
    cin >> t;
    while (t--) {
        string son, master,step_son;
        cin >> master >> son>>step_son;
        int next[son.size() + 1];
        FindNext(son, next);
        cout<<master << endl;
        if(KMP(master, son, next)!=-1)
        master.replace(KMP(master, son, next),son.size(),step_son) ;
		cout<<master<< endl;
    }
}