数据结构OJ实验5-串应用

A. DS串应用--KMP算法

题目描述

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

输入

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

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

以此类推

输出

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

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

以此类推

样例查看模式?

正常显示查看格式

输入样例1?

3
qwertyuiop
tyu
aabbccdd
ccc
aaaabababac
abac

输出样例1

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

AC代码

#include<iostream>
#include<string>
#include<vector>
using namespace std;
class Mystring
{
	string mains;
	string p;
	vector<int>next;
public:
	Mystring()
	{
		cin >> mains >> p;
		next.resize(p.size());
		//得到next数组
		int m = p.size();
		next[0] = -1;
		int j = 0, k = -1;
        //j为待匹配的主串，k为匹配串
		while (j < m - 1)
		{
			if (k == -1 || p[k] == p[j])
			{
				k++;
				j++;
				next[j] = k;
			}
			else
			{
				k = next[k];
			}
		}
	}
	void showNext()
	{
		for (int i = 0; i < p.size(); i++)
		{
			cout << next[i] << " ";
		}
		cout << endl;
	}
	void kmp()
	{
		int m = mains.length();
		int n = p.length();
		int i = 0, j = -1;
        //i为待匹配的主串，j为匹配串
		while (i < m && j < n)
		{
			if (j == -1 || mains[i] == p[j])
			{
				i++;
				j++;
			}
			else
			{
				j = next[j];
			}
		}
		if (j >= n)//匹配成功
		{
			cout << i - n + 1 << endl;//注意加一！答案下标从1开始
		}
		else
		{
			cout << 0 << endl;
		}
	}
};
int main()
{
	int t;
	cin >> t;
	while (t--)
	{
		Mystring my;
		my.showNext();
		my.kmp();
	}
	return 0;
}

B. DS串应用--串替换

题目描述

给出主串、模式串、替换串，用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

AC代码

#include<iostream>
#include<string>
#include<vector>
using namespace std;
class Mystring
{
	string mains;
	string p;
	vector<int>next;
public:
	Mystring()
	{
		cin >> mains >> p;
		next.resize(p.size());
		//得到next数组
		int m = p.size();
		next[0] = -1;
		int j = 0, k = -1;
		while (j < m - 1)
		{
			if (k == -1 || p[k] == p[j])
			{
				k++;
				j++;
				next[j] = k;
			}
			else
			{
				k = next[k];
			}
		}
	}
	void showNext()
	{
		for (int i = 0; i < p.size(); i++)
		{
			cout << next[i] << " ";
		}
		cout << endl;
	}
	int kmpFind()
	{
		int m = mains.length();
		int n = p.length();
		int i = 0, j = 0;//注意j=0开头!
		while (i < m && j < n)
		{
			if (j == -1 || mains[i] == p[j])//注意j=-1!
			{
				i++;
				j++;
			}
			else
			{
				j = next[j];
			}
		}
		if (j >= n)
		{
			return i - n;
		}
		else
		{
			return -1;
		}
	}
	void replaceS(string rp)
	{
		cout << mains << endl;
		int idx = kmpFind();
		if (idx == -1)
		{
			cout << mains << endl;
			return;
		}
		string temp = mains.substr(0, idx);//但是不包括idx那个字符
		temp += rp;
		temp += mains.substr(idx + p.size());//到最后
		cout << temp << endl;
	}
};
int main()
{
	int t;
	cin >> t;
	while (t--)
	{
		Mystring my;
		string rp;
		cin >> rp;
		my.replaceS(rp);
	}
	return 0;
}

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。

样例查看模式?

正常显示查看格式

输入样例1?

6
a
ab
abc
abcd
abcda
abcdab

输出样例1

empty
empty
empty
empty
a
ab

AC代码

#include<iostream>
#include<string>
#include<vector>
using namespace std;
class Mystring
{
	string p;
	vector<int>next;
public:
	Mystring()
	{
		cin >>  p;
		p += '#';//便于找公共前后缀长度
		next.resize(p.size());
		//得到next数组
		int m = p.size();
		next[0] = -1;
		int j = 0, k = -1;
		while (j < m-1)
		{
			if (k == -1 || p[k] == p[j])
			{
				k++;
				j++;//加了之后就能遍历到最后一个m-1下标的字符了
				next[j] = k;
			}
			else
			{
				k = next[k];
			}
		}
	}
	void showNext()
	{
		for (int i = 0; i < p.size(); i++)
		{
			cout << next[i] << " ";
		}
		cout << endl;
	}
	void getans()
	{
		int idx = p.size() - 1;
		if (next[idx] == -1||next[idx]==0)
		{
			cout << "empty" << endl;
		}
		else
		{
			string ans = p.substr(0, next[idx]);
			cout << ans << endl;
		}
	}
};
int main()
{
	int t;
	cin >> t;
	while (t--)
	{
		Mystring my;
		my.getans();
	}
	return 0;
}

D. DS串应用—最长重复子串

题目描述

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

输入

测试次数t

t个测试串

输出

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

样例查看模式?

正常显示查看格式

输入样例1?

3
abcaefabcabc
szu0123szu
szuabcefg

输出样例1

4
3
-1

AC代码

#include<iostream>
#include<string>
using namespace std;
int main()
{
	int t;
	cin >> t;
	while (t--)
	{
		string s;
		cin >> s;
		int maxl = -1;
		int n = s.length();
		for (int i = 0; i < n; i++)
		{
			for (int j = 1; j <= n; j++)
			{
				string temp = s.substr(i, j);
				int pos = s.find(temp, i+temp.length());//从后面开始找
				if (pos == -1)
				{
					continue;
				}
				if (maxl < (int)temp.length())//注意比较时一定要加上(int)
				{
					maxl = temp.length();
				}
			}
		}
		cout << maxl << endl;
	}
	return 0;
}

E. 可重叠子串 (Ver. I)

题目描述

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

输入

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

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

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

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

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

输出

对于每组测试数据，

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

具体输出见样例

样例查看模式?

正常显示查看格式

输入样例1

2
aabbcc
3
aa
bb
cc
ababab
1
aba

输出样例1

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

AC代码

#include<iostream>
#include<string>
using namespace std;
#include<iostream>
#include<string>
#include<vector>
using namespace std;
class Mystring
{
	string p;
	vector<int>next;
public:
	Mystring()
	{
		cin >> p;
		p += '#';//便于找公共前后缀长度
		next.resize(p.size());
		//得到next数组
		int m = p.size();
		next[0] = -1;
		int j = 0, k = -1;
		while (j < m - 1)
		{
			if (k == -1 || p[k] == p[j])
			{
				k++;
				j++;//加了之后就能遍历到最后一个m-1下标的字符了
				next[j] = k;
			}
			else
			{
				k = next[k];
			}
		}
	}
	int getans()
	{
		int idx = p.size() - 1;
		if (next[idx] == -1 || next[idx] == 0)
		{
			return 0;
		}
		else
		{
			string ans = p.substr(0, next[idx]);
			return ans.size();
		}
	}
	string gets()
	{
		string temp = p.substr(0, p.size() - 1);
		return temp;
	}
};
void getans(string s, Mystring my)
{
	int i = 0;
	int ans = 0;
	while (i < s.size())
	{
		if (s.find(my.gets(),i) != -1)
		{
			ans++;
			i = s.find(my.gets(), i);
			i += my.gets().length() - my.getans();
		}
		else break;
	}
	cout << my.gets() << ":" << ans << endl;
}
int main()
{
	int t;
	cin >> t;
	while (t--)
	{
		string s;
		cin >> s;
		int n;
		cin >> n;
		for (int i = 0; i < n; i++)
		{
			Mystring my;
			getans(s, my);
		}
	}
	return 0;
}