DS|串应用

问题一：DS串应用 -- KMP算法

题目描述：

学习KMP算法，给出主串和模式串，求模式串在主串的位置

输入要求：

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

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

以此类推

输出要求：

第一行输出第1个实例的模式串的next值

第二行输出第1个实例的匹配位置，位置从1开始计算，如果匹配成功输出位置，匹配失败输出0

以此类推

输入样例：

3
qwertyuiop
tyu
aabbccdd
ccc
aaaabababac
abac

输出样例：

-1 0 0 
5
-1 0 1 
0
-1 0 0 1 
8

代码示例：

#include <iostream>
#include <string>
#include <cstring>
#include <iomanip>
#include <algorithm>
using namespace std;

int ne[10010] = { 0 };

void getNext(string str) {
    int j = 0, k = -1;
    ne[0] = -1;
    while (j < str.size() - 1) {
        if (k == -1 || str[j] == str[k]) {
            j++, k++;
            ne[j] = k;
        }
        else k = ne[k];
    }

    for (int i = 0; i < str.size(); i++) cout << ne[i] << " ";
    cout << endl;
}

bool fewwerSize(string str, int x) {
    int strlength = str.size();
    if (x < strlength) return true;
    else return false;
}

int KMP(string s, string p) {
    int i = 0, j = 0;
    while (fewwerSize(s, i) && fewwerSize(p, j)) {
        if (j == -1 || s[i] == p[j]) i++, j++;
        else j = ne[j];
    }
    return j >= p.size() ? (i - p.size()) : -1;
}

int main() {
    int t;
    cin >> t;
    while (t--) {
        string s, p;
        cin >> s >> p;

        getNext(p);
        int result = KMP(s, p);
        if (result != -1) cout << result + 1 << endl;
        else cout << "0" << endl;
    }
    return 0;
}

问题二：DS串应用 -- 串替换

题目描述：

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

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

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

输入要求：

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

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

以此类推

输出要求：

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

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

以此类推

输入样例：

3
aabbccdd
bb
ff
aaabbbccc
ddd
eee
abcdef
abc
ccccc

输出样例：

aabbccdd
aaffccdd
aaabbbccc
aaabbbccc
abcdef
cccccdef

代码示例：

#include <iostream>
#include <string>
#include <cstring>
#include <iomanip>
#include <algorithm>
using namespace std;

int ne[10010] = { 0 };

void getNext(string str) {
    int j = 0, k = -1;
    ne[0] = -1;
    while (j < str.size() - 1) {
        if (k == -1 || str[j] == str[k]) {
            j++, k++;
            ne[j] = k;
        }
        else k = ne[k];
    }

    //for (int i = 0; i < str.size(); i++) cout << ne[i] << " ";
    //cout << endl;
}

bool fewwerSize(string str, int x) {
    int strlength = str.size();
    if (x < strlength) return true;
    else return false;
}

int KMP(string s, string p) {
    int i = 0, j = 0;
    while (fewwerSize(s, i) && fewwerSize(p, j)) {
        if (j == -1 || s[i] == p[j]) i++, j++;
        else j = ne[j];
    }
    return j >= p.size() ? (i - p.size()) : -1;
}

int main() {
    int t;
    cin >> t;
    while (t--) {
        string s, p, ps;
        cin >> s >> p >> ps;
        cout << s << endl;
        getNext(p);
        int result = KMP(s, p);
        if (result != -1) {
            s.erase(result, p.size());
            s.insert(result, ps);
        }
        cout << s << endl;
    }
    return 0;
}

问题三：DS串应用 -- 计算串的最长的真前后缀

题目描述：

给定一个串，如ABCDAB，则ABCDAB的真前缀有：{ A, AB,ABC, ABCD, ABCDA }ABCDAB的真后缀有：{ B, AB,DAB, CDAB, BCDAB } 因此，该串的真前缀和真后缀中最长的相等串为AB，我们称之为该串的“最长的真前后缀”。试实现一个函数string matched_Prefix_Postfix(string str)，得到输入串str的最长的真前后缀。若不存在最长的真前后缀则输出empty

输入要求：

第1行：串的个数 n第2行到第n+1行：n个字符串

输出要求：

n个最长的真前后缀，若不存在最长的真前后缀则输出empty。

输入样例：

6
a
ab
abc
abcd
abcda
abcdab

输出样例：

empty
empty
empty
empty
a
ab

代码示例：

#include<iostream>
#include<string>
#include<cmath>
using namespace std;

string matched_Prefix_Postfix(string str){
	if (str.length() == 1) return "-1";
	string prestr, poststr, ans = "-1";
	int j = 0, pos = str.length() - 1;
	while (j < str.length() - 1){
		prestr = str.substr(0, j + 1), poststr = str.substr(pos - j, pos);
		j++;
		if (prestr == poststr) ans = prestr;
	}
	return ans;
}

int main(){
	int t;
	cin >> t;
	while (t--){
		string str;
		cin >> str;
		string answer = matched_Prefix_Postfix(str);
		if (answer == "-1") cout << "empty" << endl;
		else cout << answer << endl;
	}
	return 0;
}

问题四：DS串应用 -- 最长重复子串

题目描述：

求串的最长重复子串长度（子串不重叠）。例如：abcaefabcabc的最长重复子串是串abca，长度为4。

输入要求：

测试次数t

t个测试串

输出要求：

对每个测试串，输出最长重复子串长度，若没有重复子串，输出-1.

输入样例：

3
abcaefabcabc
szu0123szu
szuabcefg

输出样例：

4
3
-1

代码示例：

#include <iostream>
#include <string>
#include <cstring>
#include <iomanip>
#include <algorithm>
using namespace std;

int main() {
    int t;
    cin >> t;
    while (t--) {
        bool mark = false;
        int maxLen;
        string str;
        cin >> str;
        int strlen = str.length();

        for (int i = strlen / 2; i > 0; i--) {
            for (int j = 0; j < strlen - i; j++) {
                string str = str.substr(j, i);
                if (str.find(str, i + j) != string::npos) {//为什么从i+j开始找，因为字串不重叠
                    mark = true;
                    maxLen = i;
                    break;
                }
            }
            if (mark) break;
        }

        if (mark) cout << maxLen << endl;
        else cout << "-1" << endl;
    }
}

问题五：DS串应用 -- 可重叠子串

题目描述：

给定一个字符串（模式串）和一些待查找的字符串，求每个待查找字符串在模式串中出现的次数（可重叠）

输入要求：

第一行输入t，表示有t组测试数据

每一组测试数据包含多行：

每一组的第一行包括一个字符串P，长度不超过105，且非空串

每一组的第二行包括一个整数N，代表待查找的字符串数量 (1 <= N <= 5)

每一组接下来的N行，每一行包括一个待查找的字符串，其长度不超过50，且非空串

输出要求：

对于每组测试数据，

输出每个待查找字符串出现的次数，

具体输出见样例

输入样例：

2
aabbcc
3
aa
bb
cc
ababab
1
aba

输出样例：

aa:1
bb:1
cc:1
aba:2

代码示例：

#include <iostream>
#include <string>
#include <cstring>
#include <iomanip>
#include <algorithm>
using namespace std;

int main() {
    int t;
    cin >> t;
    while (t--) {
        bool mark = false;
        string p;
        cin >> p;
        int lenp = p.length();

        int n;
        cin >> n;
        string* str = new string[n];
        for (int i = 0; i < n; i++) cin >> str[i];

        for (int i = 0; i < n; i++) {
            int cnt = 0;
            string tmp = p;
            for (int j = 0; j < p.length(); j++) {
                string sstr = tmp.substr(0, str[i].size());
                if (str[i] == sstr) cnt++;
                tmp.erase(0, 1);
            }
            cout << str[i] << ":" << cnt << endl;
        }
    }
}