目录
【id:54】【10分】A. 串应用- 计算一个串的最长的真前后缀
【id:56】【20分】C. 子串循环问题 (Ver. I)
【id:54】【10分】A. 串应用- 计算一个串的最长的真前后缀
时间限制1s
内存限制128MB
题目描述
给定一个串，如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。
#include <iostream>
#include<string>
using namespace std;
int main() {
int n;
cin >> n;
for (int i = 0; i < n; i++) {
string str;
cin >> str;
if (str.length() == 1) {
cout << ("empty") << endl;
}
else {
int len = str.length();
int t=0;//个数
int flog1 = 0;
for (int j = len-1; j >=1 ; j--) {//找前缀和后缀
int flog2 = 1;
for (int k = len - j; k <len; k++) {
if (str[k] != str[t]) {
flog2 = 0;
}
t++;
}
if (flog2 == 1) {
for (int y = 0; y < j; y++) {
cout << str[y];
}
cout << endl;
flog1 = 1;
break;
}
t = 0;
}
if (flog1 == 0) {
cout << "empty" << endl;
}
}
}
return 0;
}【id:55】【10分】B. DS串应用—最长重复子串
时间限制1s
内存限制128MB
题目描述
求串的最长重复子串长度（子串不重叠）。例如：abcaefabcabc的最长重复子串是串abca，长度为4。
输入
测试次数t
t个测试串
输出
对每个测试串，输出最长重复子串长度，若没有重复子串，输出-1.
#include <iostream>
#include<string>
using namespace std;
int main() {//注意不重叠
int t;
cin >> t;
while (t--) {
string str;
cin >> str;
int len = str.length();//获取长度
int flog = 0;
for (int i = len/2; i >= 1;i-- ) {//i为长度,从最长到1
for (int j = 0; j <= len - i-1;j++ ) {//j是起点
for (int k = j + 1; k <= len - i; k++) {//k是j的后面相同长度的字符串
//cout << i << " " << j << " " << k << endl;
if (str.substr(j, i) == str.substr(k, i)) {//如果相等
cout << i << endl;
flog = 1;
break;
}
}
if (flog == 1) {
break;
}
}
if (flog == 1) {
break;
}
}
if (flog == 0) {
cout << "-1" << endl;
}
flog = 0;
}
return 0;
}【id:56】【20分】C. 子串循环问题 (Ver. I)
题目描述
给定一个字符串，求需要添加至少几个字符到字符串末尾才能使得整个字符串由某一个不为本身的子串循环构成？
如"abca"，添加"bc"后构成"abcabc"，其由子串"abc"循环构成;也可以添加"abca"后构成"abcaabca"，其由子串"abca"循环构成，相比之下"bc"只有2个字符，添加的字符量最少。
输入
第一行包括一个整数T(1 <= T <= 100)，代表测试组数
每组测试数据包括一行字符串，其长度范围为 [3, 104]
输出
对于每组测试数据
输出一个整数N，代表添加的最小字符数量
思路：大致意思就是我们加上最少的字符数量，让这个输入的字符串变成一个循环的字符串。
我们这样想。怎么才能找到目标的循环链结呢 比如 aaa 的循环链结 a abca 的循环链结 abc
还有 abcdefg 的循环链结 abcdefg ？
最底层的思想就是得到字符串的长度 然后依次遍历 比如 ababa 得到长度1，2，3，4，5
以1为步长开始 a b a 依次比较发现不相等 再以2 为步长 ab ab 余数a 发现前面相等 然后余数a与链结ab的第一个相等 就可以输出 链结长-余数长（2-1）即为所求答案的1.
如果aaa这种 她最后面起点跟len一样了 就直接输出 0 表示本身就对称
如果是abcdefg这种找不到循环链结的 就输出其本身长度 7
#include <iostream>
#include<string>
using namespace std;
int main() {
int t;
cin >> t;
while (t--) {
string str;//定义字符串
cin >> str;//输入
int len = str.length();//得到字符串长度
for (int i = 1; i <= len;i++) {//长度
int flog = 1, n=0, flog2=0;//flog是判断是否有不同 n是下标 flog2 是判断有没有进循环
for (int j = 0; j < (len / i)-1;j++) {//次数
flog2 = 1;//进循环
if (n+i<len-i&&str.substr(n, i) != str.substr(n + i, i)||n+i>=len) {
//如果下一个起点坐标超过了len-1，直接flog=0，或者没超过，但是不相等也给flog赋值为0。
flog = 0;
}
n += i;//下标++位移
}
if (flog==1) {//要么前面都对称，只剩余数，要么前面都不对称但是超范围了
if (flog2 == 0) {//没进循环 代表超过了范围
n += i;//先移动下标
if (str.substr(n, len - n) == str.substr(0, len - n)) {//如果有相等 比如说abcdea 这里最后一个a与前面第一个一样
cout << i - (len - n) << endl;
break;
}
}
if (str.substr(n, len - n) == str.substr(0, len - n)) {//前面都对称，只剩余数
n += i;
if (n == len) {//处理特殊情况 如aaaaaa 本身就对称 n再+=1 刚好等于len
cout << "0" << endl;
break;
}
cout << i - (len - n) << endl;//处理正常情况
break;
}
}
if (i==len) {//如果到最长了都没有找到可以对称的 那么就要加一个它本身一样的字符串才能构成对称
cout << i << endl;
}
}
}
return 0;
}【id:53】【20分】D. DS串应用--串替换
时间限制1s
内存限制128MB
题目描述
给出主串、模式串、替换串，用KMP算法找出模式串在主串的位置，然后用替换串的字符替换掉模式串
本题只考虑一处替换的情况，如果你想做的完美一些，能够实现多处替换那
可能需要考虑模式串和替换串长度不一致的情况
输入
第一个输入t，表示有t个实例
第二行输入第1个实例的主串，第三行输入第1个实例的模式串，第四行输入第1个实例的替换串
以此类推
输出
第一行输出第1个实例的主串
第二行输出第1个实例的主串替换后结果，如果没有发生替换就输出主串原来的内容。
以此类推
#include <iostream>
#include <string>
using namespace std;
class MyString
{
private:
string dad;
int len1;
public:
MyString(string str=" ") {
dad = str;
len1 = dad.length();
}
int findkmp(string son);
void display() {
cout << dad << endl;
}
};
void getnext(int *next,string son,int len) {
next[0] = 0;
int i = 1;
int j = 0;
for (i; i < len; i++) {
while (j > 0 && son[i] != son[j]) {
j--;
}
if (son[i] == son[j]) {
j++;
next[i] = j;
}
else {
next[i] = j;
}
}
}
int MyString::findkmp(string son) {
int len=son.length();
int* next = new int[len];
getnext(next,son,len);//填充next数组
int i = 0,j = 0;
while (i < len1) {
if (dad[i] == son[j]) {//如果相同则i和j都增加
j++;
i++;
}
else if (j > 0) {//如果不同，则根据next的值来决定跳过多少个字符来比较
j = next[j - 1];
}
else {
i++;
}
if (j == len) {
return i - j;
}
}
return -1;
}
int main()
{
int t;
cin >> t;
while (t--) {
string dad, son;
cin >> dad >> son;
MyString s(dad);
s.display();
int setnum = s.findkmp(son);
string str;
cin >> str;
int len2 = str.length(),len1=son.length();
if (setnum == -1) {
cout << dad << endl;
}
else {
dad.replace(setnum, len1, "");
dad.insert(setnum, str);
cout << dad << endl;
}
}
return 0;
}【id:52】【20分】E. DS串应用--KMP算法
时间限制1s 内存限制128MB题目描述
学习KMP算法，给出主串和模式串，求模式串在主串的位置
算法框架如下，仅供参考
输入
第一个输入t，表示有t个实例
第二行输入第1个实例的主串，第三行输入第1个实例的模式串
以此类推
输出
第一行输出第1个实例的模式串的next值
第二行输出第1个实例的匹配位置，位置从1开始计算，如果匹配成功输出位置，匹配失败输出0
以此类推
#include <iostream>
#include <string>
using namespace std;
class MyString
{
private:
string dad;
int len1;
public:
MyString(string str=" ") {
dad = str;
len1 = dad.length();
}
int findkmp(string son);
};
void getnext(int *next,string son,int len) {
next[0] = 0;
int i = 1;
int j = 0;
for (i; i < len; i++) {
while (j > 0 && son[i] != son[j]) {
j--;
}
if (son[i] == son[j]) {
j++;
next[i] = j;
}
else {
next[i] = j;
}
}
}
void nextshow(int next[], int len) {
int* next1 = new int[len];
next1[0] = -1;
for (int i = 1; i < len; i++) {
next1[i] = next[i - 1];
}
for (int i = 0; i < len; i++) {
cout << next1[i] << " ";
}
cout << endl;
}
int MyString::findkmp(string son) {
int len=son.length();
int* next = new int[len];
getnext(next,son,len);//填充next数组
nextshow(next,len);//展示next
int i = 0,j = 0;
while (i < len1) {
if (dad[i] == son[j]) {//如果相同则i和j都增加
j++;
i++;
}
else if (j > 0) {//如果不同，则根据next的值来决定跳过多少个字符来比较
j = next[j - 1];
}
else {
i++;
}
if (j == len) {
return i - j;
}
}
return -1;
}
int main()
{
int t;
cin >> t;
while (t--) {
string dad, son;
cin >> dad >> son;
MyString s(dad);
int setnum = s.findkmp(son);
int len1=son.length();
if (setnum == -1) {
cout << "0" << endl;
}
else {
cout << setnum+1 << endl;
}
}
return 0;
}【id:57】【20分】F. 可重叠子串 (Ver. I)
时间限制1s
内存限制128MB
题目描述
给定一个字符串（模式串）和一些待查找的字符串，求每个待查找字符串在模式串中出现的次数（可重叠）
输入
测试数据有多组（测试组数 <= 5），
第一行包括一个字符串P，长度不超过105，且非空串
第二行包括一个整数N，代表待查找的字符串数量 (1 <= N <= 5)
接下来的N行，每一行包括一个待查找的字符串，其长度不超过50，且非空串
输出
对于每组测试数据，
输出每个待查找字符串出现的次数，
具体输出见样例
标签：string,int,len,son,next,实验,str,数据结构,串及 From： https://blog.csdn.net/2301_81149434/article/details/143054592