【数据结构】串的应用

Alex_Shen
2020-11-07 / 0 评论 / 0 点赞 / 80 阅读 / 5,445 字 / 正在检测是否收录...
温馨提示:
本文最后更新于 2022-04-06,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。

问题 A: 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 {
	string mainstr;
	int size;
	void GetNext(string p, int next[]);
	int KMPFind(string str, int next[]);
public:
	MyString();
	~MyString();
	void SetVal(string sp);
	int KMPFindSubStr(string p, int pos);
};

int main() {
	int N;
	cin >> N;
	while (N--) {
		MyString String;
		string p;
		cin >> p;
		String.SetVal(p);
		cin >> p;
		cout << String.KMPFindSubStr(p, 0) << endl;
	}
	return 0;
}

void MyString::GetNext(string p, int next[])
{
	int i = 0, L = p.length(), j = -1;
	next[0] = -1;
	while (i < L) {
		if (j == -1 || p[i] == p[j]) {
			i++, j++;
			next[i] = j;
		}
		else
			j = next[j];
	}
}

int MyString::KMPFind(string str, int next[])
{
	int i = 0, j = 0;
	int len = str.size();
	while (j < len && i < mainstr.length()) {
		if (j == -1 || mainstr[i] == str[j]) {
			i++;
			j++;
		}
		else {
			j = next[j];
		}
		if (j == str.size())
			return i - j + 1;
	}

	return 0;
}

MyString::MyString()
{
	size = 0;
	mainstr = "";
}

MyString::~MyString()
{
	size = 0;
	mainstr = "";
}

void MyString::SetVal(string sp)
{
	mainstr = "";
	mainstr.append(sp);
	size = mainstr.length();
}

int MyString::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, next);
	return v;
}

问题 B: 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>
using namespace std;

class MyString {
	string mainstr;
	int size;
	void GetNext(string p, int next[]);
	int KMPFind(string str, int next[]);
public:
	MyString();
	~MyString();
	void SetVal(string sp);
	int KMPFindSubStr(string p, int pos);
	void printStr();
};

int main() {
	int N;
	cin >> N;
	while (N--) {
		MyString String;
		string p1, p2, str;
		cin >> str;
		String.SetVal(str);
		cin >> p1 >> p2;
		String.printStr();
		if (String.KMPFindSubStr(p1, 0) != 0) {
			str.replace(String.KMPFindSubStr(p1, 0) - 1, p1.length(), p2);
		}
		cout << str << endl;
	}
	return 0;
}

void MyString::GetNext(string p, int next[])
{
	int i = 0, L = p.length(), j = -1;
	next[0] = -1;
	while (i < L) {
		if (j == -1 || p[i] == p[j]) {
			i++, j++;
			next[i] = j;
		}
		else
			j = next[j];
	}
}

int MyString::KMPFind(string str, int next[])
{
	int i = 0, j = 0;
	int len = str.size();
	while (j < len && i < mainstr.length()) {
		if (j == -1 || mainstr[i] == str[j]) {
			i++;
			j++;
		}
		else {
			j = next[j];
		}
		if (j == str.size())
			return i - j + 1;
	}

	return 0;
}

MyString::MyString()
{
	size = 0;
	mainstr = "";
}

MyString::~MyString()
{
	size = 0;
	mainstr = "";
}

void MyString::SetVal(string sp)
{
	mainstr = "";
	mainstr.append(sp);
	size = mainstr.length();
}

int MyString::KMPFindSubStr(string p, int pos)
{
	int L = p.length();
	int* next = new int[L];
	GetNext(p, next);
	int v = -1;
	v = KMPFind(p, next);
	return v;
}

void MyString::printStr()
{
	cout << mainstr << endl;
}

问题 C: 串应用- 计算一个串的最长的真前后缀

题目描述

给定一个串,如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>
using namespace std;

string matched_Prefix_Postfix(string str) {
	int len = str.length() - 1;
	int frontPos = 0, backPos = str.length(), i = 1;
	string temp = "empty";
	while (len--) {
		if (str.substr(frontPos, i) == str.substr(backPos - i, i)) {
			temp = str.substr(frontPos, i);
		}
		i++;
	}
	return temp;
}

int main() {
	int N;
	cin >> N;
	while (N--) {
		string str;
		cin >> str;
		cout << matched_Prefix_Postfix(str) << endl;
	}
	return 0;
}

问题 D: DS串应用—最长重复子串

题目描述

求串的最长重复子串长度(子串不重叠)。例如:abcaefabcabc的最长重复子串是串abca,长度为4。

输入

测试次数t
t个测试串

输出

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

样例输入

3
abcaefabcabc
szu0123szu
szuabcefg

样例输出

4
3
-1

题解

#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
using namespace std;

int findMax(string str) {
    int L = str.size();
    int max = -1;
    for (int i = 0; i < L; i++)
    {
        for (int j = i; j < L; j++)
        {
            string p = str.substr(i, j - 1);
            string temp = str;
            int index = str.find(p) + 1;
            int slen = str.size();
            int plen = p.size();
            string S = str.substr(0, index - 1);
            string temp2 = str.substr(index - 1 + plen, slen);
            S += temp2;
            if (S.find(p)!=-1)
            {
                int t = plen;
                if (t > max)
                    max = t;
            }
            str = temp;
        }
    }
    if (max == 0)
        return -1;
    return max;
}

int main() {
	int N;
	cin >> N;
	while (N--) {
		string str;
		cin >> str;
		cout << findMax(str) << endl;
	}
	return 0;
}

问题 E: 子串循环问题 (Ver. I)

题目描述

给定一个字符串,求需要添加至少几个字符到字符串末尾才能使得整个字符串串由某一个不为本身的子串循环构成?
如"abca",添加"bc"后构成"abcabc",其由子串"abc"循环构成;也可以添加"abca"后构成"abcaabca",其由子串"abca"循环构成,相比之下"bc"只有2个字符,添加的字符量最少。

输入

第一行包括一个整数T(1 <= T <= 100),代表测试组数
每组测试数据包括一行字符串,其长度范围为 [3, 10^4]

输出

对于每组测试数据
输出一个整数N,代表添加的最小字符数量

样例输入

3
aaa
abca
abcdefg

样例输出

0
2
7

题解

#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
using namespace std;

void GetNext(string p, int next[])
{
	int i = 0, L = p.length(), j = -1;
	next[0] = -1;
	while (i < L) {
		if (j == -1 || p[i] == p[j]) {
			i++, j++;
			next[i] = j;
		}
		else
			j = next[j];
	}
}

int findMin(string str) {
	int len = str.size();
	int* next = new int[len + 1];
	GetNext(str, next);
	int i = len - next[len];
	int j = i - len % i;
	if (i != len && len % i == 0)
		j = 0;
	return j;
}

int main() {
	int N;
	cin >> N;
	while (N--) {
		string str;
		cin >> str;
		cout << findMin(str) << endl;
	}
	return 0;
}

0

评论区