1. 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> using namespace std; class myString { private: string mainstr; int size; void getnext(string p, int next[]) { int j = 0; int k = -1; next[j] = k; int len = p.length(); while (j < len - 1) { if (k == -1 || p[j] == p[k]) { j++; k++; next[j] = k; } else { k = next[k]; } } } int KMPfind(string p, int pos, int next[]) { int i = pos; int j = 0; int len = p.length(); while (i < size && j < len) { if (j == -1 || mainstr[i] == p[j]) { i++; j++; } else { j = next[j]; } } if (j >= len) return i - len; else { return -1; } } public: myString() { size = 0; mainstr = ""; } ~myString() { size = 0; mainstr = ""; } void setval(string sp) { mainstr.assign(sp); size = mainstr.length(); } int KMPfindSubstr(string p, int pos) { int i; int L = p.length(); int *next = new int[L]; getnext(p, next); for (i = 0; i < L; i++) { cout << next[i] << ' '; } cout << endl; int v = -1; v = KMPfind(p, pos, next); delete[] next; return v + 1; } }; int main() { int t; cin >> t; while (t--) { string a, b; cin >> a >> b; myString p; p.setval(a); cout << p.KMPfindSubstr(b, 0) << endl; } return 0; }
2. DS串应用–串替换
题目描述
给出主串、模式串、替换串，用KMP算法找出模式串在主串的位置，然后用替换串的字符替换掉模式串
本题只考虑一处替换的情况，如果你想做的完美一些，能够实现多处替换那
可能需要考虑模式串和替换串长度不一致的情况
输入
第一行输入先输入n表示客户数量
第二行输入每个客户的类型，数据之间用用空格隔开
第三行输入每个客户的办理时间，数据之间用用空格隔开
输出
第一行输出第1个实例的主串
第二行输出第1个实例的主串替换后结果，如果没有发生替换就输出主串原来的内容。
以此类推
输入样例
3
aabbccdd
bb
ff
aaabbbccc
ddd
eee
abcdef
abc
ccccc
输出样例
aabbccdd
aaffccdd
aaabbbccc
aaabbbccc
abcdef
cccccdef
参考代码
#include <iostream> #include <string> using namespace std; class myString { public: string mainstr; int size; void getnext(string p, int next[]) { int j = 0; int k = -1; next[j] = k; int len = p.length(); while (j < len - 1) { if (k == -1 || p[j] == p[k]) { j++; k++; next[j] = k; } else { k = next[k]; } } } int KMPfind(string p, int pos, int next[]) { int i = pos; int j = 0; int len = p.length(); while (i < size && j < len) { if (j == -1 || mainstr[i] == p[j]) { i++; j++; } else { j = next[j]; } } if (j >= len) return i - len; else { return -1; } } myString() { size = 0; mainstr = ""; } ~myString() { size = 0; mainstr = ""; } void setval(string sp) { mainstr.assign(sp); size = mainstr.length(); } int KMPfindSubstr(string p, int pos) { int i; int L = p.length(); int *next = new int[L]; getnext(p, next); int v = -1; v = KMPfind(p, pos, next); delete[] next; return v + 1; } void replace(string p, int pos,string c) { string result = ""; result += mainstr.substr(0, pos-1); result += p; result += mainstr.substr(pos-1+c.length(), mainstr.length()); mainstr = result; } }; int main() { int t; cin >> t; while (t--) { string a, b, c; cin >> a >> b >> c; myString p; p.setval(a); cout << p.mainstr << endl; int num = p.KMPfindSubstr(b, 0); if (num != 0) p.replace(c, num,b); cout << p.mainstr << endl; } }
3. DS串应用—最长重复子串
题目描述
求串的最长重复子串长度（子串不重叠）。例如：abcaefabcabc的最长重复子串是串abca，长度为4。
输入
测试次数t
t个测试串
输出
对每个测试串，输出最长重复子串长度，若没有重复子串，输出-1.
输入样例
3
abcaefabcabc
szu0123szu
szuabcefg
输出样例
4
3
-1
参考代码
#include <iostream> #include <string> using namespace std; int main() { string s, subr, subl; int t; int i, flag, j; cin >> t; while (t--) { cin >> s; int len = s.length(); for (i = len / 2, flag = 0; i >= 1 && !flag; i--) for (j = 0; j < len - 2 * i; j++) { subl = s.substr(j, i); subr = s.substr(i + j); if (subr.find(subl) != string::npos) { cout << i << endl; flag = 1; break; } } if (!flag) cout << -1 << endl; } return 0; }
