吉林大学2023级数据结构上机实验第（1~2周）参考答案（关注我，在系统关闭后持续更新）

A 括号匹配（进阶版）

分数 10

编写程序检查给定字符串中包含的括号是否正确匹配，本题中的括号有{ }、[ ]、( )、< >四种。另外再加上一个新的约束条件：当有多种括号嵌套时，嵌套的顺序应为{ → [ → ( → <，即a–g+b∗[(d∗<e–f>)]、a+[b+(c–d)∗e]都是正确的匹配，而a+(b∗[c+d])则不是正确匹配。注意本题不允许相同类型括号的嵌套，即a+(b∗(c+d))不是正确匹配。本题不需要判断表达式是否合法，只需判断字符串中包含的括号是否正确匹配。

输入格式:

第一行为一个整数n，表示字符串的个数。接下来n行，每行为一个字符串。1<n≤100，字符串长度不超过1000。

输出格式:

对于每个字符串，若为正确匹配则输出"Match" ，若不匹配则输出"Fail"。

输入样例1:
8
a+(b*[c+d])
g{b[(<c>)d]e}x
[()]
((()))
<>()[]{}
[{}]
x=y+{z+(b)}
][()
输出样例1:
Fail
Match
Match
Fail
Match
Fail
Match
Fail
输入样例2:
6
{[afds(a<afd>)]}yt
[()rew]
<>()[wre]{}
[{qw}]
rew{(weq)}jjk
<><{}>[][](){[{}]}
输出样例2:
Match
Match
Match
Fail
Match
Fail

#include<iostream>
#include<cstring>
#include<algorithm>
#include<stack>
using namespace std;
const int N = 10010;
int n;bool pan(string s) {stack<char>stk;for (int i = 0; i < s.size(); i++) {if (s[i] == '{') {if (stk.size() && (stk.top() == '[' || stk.top() == '(' || stk.top() == '<'|| stk.top() == '{')) {return false;}else {stk.push(s[i]);}}if (s[i] == '}') {if (!stk.size() || stk.top() != '{') {return false;}else {stk.pop();}}if (s[i] == '[') {if (stk.size()&&(stk.top() == '(' || stk.top() == '<'|| stk.top() == '[')) {return false;}else {stk.push(s[i]);}}if (s[i] == ']') {if (!stk.size() || stk.top() != '[') {return false;}else {stk.pop();}}if (s[i] == '(') {if (stk.size()  && (stk.top() == '<'||stk.top()=='(')) {return false;}else {stk.push(s[i]);}}if (s[i] == ')') {if (!stk.size() || stk.top() != '(') {//cout << stk.top() << endl;return false;}else {stk.pop();}}if (s[i] == '<') {if (stk.size()&&stk.top() == '<') {return false;}else {stk.push(s[i]);}}if (s[i] == '>') {if (!stk.size()||stk.top() != '<') {return false;}else {stk.pop();}}}if (stk.size()) {return false;}else {return true;}}void solve()
{string str;cin >> str;if (pan(str)) {cout<<"Match"<<endl;}else {cout<<"Fail"<<endl;}}int main()
{ios::sync_with_stdio(0);cin.tie(0), cout.tie(0);cin >> n;while (n--) {solve();}
}

B 调皮的哈利

分数 10

贝蒂是个打字高手，打字时有不看屏幕的习惯。在一次贝蒂打字时，调皮的哈利常常趁贝蒂不注意按下Home键、End键、左右方向键和退格键。当Home键被按下时，输入光标会跳到文本最开头；当End键被按下时，输入光标会跳到文本末尾；当左/右方向键被按下时，输入光标会向左/右移动一位；当退格键被按下时，输入光标左面的一个字符会被删除。现给出贝蒂和哈利按键的字符串，其中'{'表示Home键，'}'表示End键，'<'表示左方向键，'>'表示右方向键，'#'表示退格键，其余字符均表示输入的内容，请输出屏幕上最终显示的文本。

输入格式:

输入一个字符串，长度不超过5×104，包含大小写字母、空格、下划线、{、}、<、>、#，表示贝蒂和哈利的按键序列。

输出格式:

输出为屏幕上最终显示的字符串。

输入样例1:
jlu_cc{i_love_}st
输出样例1:
i_love_jlu_ccst
输入样例2:
stre<<aaa
输出样例2:
staaare
输入样例3:
xxx>>>yyy##z<<>k
输出样例3:
xxxykz
输入样例4:
abcd{efghi}jklm{nopq}rs{t}uvwxyz
输出样例4:
tnopqefghiabcdjklmrsuvwxyz

题解：

这一题暴力会超时，但是我用数组模拟指针出现了一点问题，所以我中和了两种方法过了。

希望有人能指正。

#include "bits/stdc++.h"
using namespace std;
const int N = 5e5 + 10;
string str;
list<char> L;
struct P {char c;int next;int pre;
};
P a[N];
void work1() {int now = 0;for (auto ch : str) {auto p = L.begin();switch (ch){case '#':if (now >= 1) {for (int i = 0; i < now - 1; ++i) {p++;}L.erase(p++);now--;}break;case '{':now = 0;break;case '}':now = L.size();break;case '<':now--;if (now < 0) now = 0;break;case '>':now++;if (now >= L.size()) now = L.size();break;default:for (int i = 0; i < now; i++) {p++;}L.insert(p, ch);now++;break;}}string ans = string(L.begin(), L.end());cout << ans << endl;
}
void work2() {int i = 0;int head = 0;int tail = N - 1;int pn = head;a[head].next = tail;a[head].pre = -1;a[tail].next = -1;a[tail].pre = head;while (i < str.size()) {if (str[i] == '{') {pn = head;}else if (str[i] == '}') {pn = a[tail].pre;}else if (str[i] == '<') {if (pn != head) {pn = a[pn].pre;}}else if (str[i] == '>') {if (pn != a[tail].pre) {pn = a[pn].next;}}else if (str[i] == '#') {if (pn != head) {int p = pn;pn = a[p].pre;a[pn].next = a[p].next;}}else {int now = i + 1;int ne = a[pn].next;a[now].c = str[i];a[now].next = ne;a[ne].pre = now;a[now].pre = pn;a[pn].next = now;pn = now;}i++;}pn = a[head].next;while (pn != tail) {cout << a[pn].c;pn = a[pn].next;}
}
int main()
{ios::sync_with_stdio(0);cin.tie(0), cout.tie(0);getline(cin, str);if (str.size() < 10000) {work1();}else {work2();}}

C 表达式求值

分数 10

给定一个中缀表达式，请编写程序计算该表达式的值。表达式包含+、-、*、/、^、(、)，所有运算均为二元运算，操作数均为正整数，但可能不止一位，不超过10位。运算结果为整数，值域为[−231,231)。除法运算结果若为小数则进行截尾取整。若除法运算中除数为0，则输出INVALID。幂运算须自行实现，不允许调用pow等系统函数。测试数据保证幂运算中指数为非负，底数不为0。

输入格式:

输入为多行，每行为一个长度不超过1000的字符串，表示中缀表达式。

输出格式:

对每个表达式输出一行：为一个整数（表达式的值）或为一个字符串INVALID。

输入样例:
5+(10*2)-6
8*(999+1)
1+5/(1-1)
7*2^3
输出样例:
19
8000
INVALID
56

题解：

中缀表达式求解，转后缀，可以参考我的博客中缀表达式求解，这里不赘述了。注意快速幂，或者判断特解，1的多次幂。

#include<iostream>
#include<unordered_map>
#include<stack>
#include<cstring>
using namespace std;
const int N = 1e5 + 10;
int pro[200];
stack<int>in;
stack<char>ch;
string s;
int qmi(int a, int b) {int res = 1;while (b) {if (b & 1) {res *= a;}a *= a;b >>= 1;}return res;
}
bool eval() {int b = in.top();in.pop();int a = in.top();in.pop();char c = ch.top();ch.pop();int x;if (c == '+') {x = a + b;}else if (c == '-') {x = a - b;}else if (c == '*') {x = a * b;}else if (c == '/'){if (b == 0) {return false;}else {x = a / b;}}else if (c == '^') {x = qmi(a, b);}in.push(x);return true;
}int main() {ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);pro['-']=1;pro['+']=1;pro['*']=2;pro['/']=2;pro['^']=3;while (cin >> s) {bool flag = 1;for (int i = 0;i < s.size();i++) {char c = s[i];if (!flag) {break;}if (isdigit(c)) {int x = c - '0';int j = i + 1;while (j < s.size() && isdigit(s[j])) {x = x * 10 + s[j++] - '0';}i = j - 1;in.push(x);}else if (c == '(') {ch.push('(');}else if (c == ')') {while (ch.size() && ch.top() != '(') {if (!eval()) {flag = 0;break;}}if (ch.size()) {ch.pop();}}else {while (ch.size() && pro[ch.top()] >= pro[c]) {if (!eval()) {flag = 0;break;}}ch.push(c);}}while (ch.size()) {if (!eval()) {flag = 0;break;}}if (!flag) {cout << "INVALID" << endl;while (in.size()) {in.pop();}while (ch.size()) {ch.pop();}}else {cout << in.top() << endl;in.pop();}}return 0;
}

D EDG

分数 10

2021年11月6日，英雄联盟全球总决赛打响，中国电子竞技战队Edward Gaming（EDG）以3:2力克韩国强敌DWG KIA（DK）战队，历史上首次夺得全球总冠军。一时间全网沸腾，大家纷纷在社交平台上直呼“edgnb”。现给定一段文本，请编写程序识别出连续的k个“edgnb”组成的字符串在该文本中出现了多少次。

输入格式:

第一行为1个整数T，表示数据组数。对于每组数据，第一行为1个字符串，表示给定的文本。第二行为1个整数k，含义如题目所述。（1≤T≤10。各组数据给定的字符串长度之和不超过105，且字符串中只包含a-z的小写字母。k≥1且k×5小于给定字符串长度）。

输出格式:

对于每组数据输出一行，为1个整数，表示所求的出现次数。

输入样例:
5
xyzedgnbabcedgnb
1
xyzedgnbabcedgnb
2
defedgnbedgnbxyz
2
edgnbedgnbedgnb
2
fxedgnbedgnbedgnbedgnbmem
3
输出样例:
2
0
1
2
2
数据规模:

测试点0：5≤T≤10，400≤T个字符串长度之和≤500，k=1
测试点1：5≤T≤10，400≤T个字符串长度之和≤500，k≥1
测试点2：5≤T≤10，4000≤T个字符串长度之和≤5000，k≥1
测试点3：1≤T≤3，90000≤T个字符串长度之和≤100000，k≥1
测试点4：1≤T≤3，90000≤T个字符串长度之和≤100000，k≥1

题解：

KMP就完了。

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 1e6 + 10;
char ss[10] = "edgnb";
char s[N];
char str[N];
int ne[N];
int k;
int kmp() {int ans = 0;int n = 5*k;int m = strlen(str + 1);for (int i = 2, j = 0; i <= n; i++) {while (j > 0 && s[i] != s[j + 1]) {j = ne[j];}if (s[i] == s[j + 1]) {j++;}ne[i] = j;}for (int i = 1, j = 0; i <= m; i++) {while (j > 0 && str[i] != s[j + 1]) {j = ne[j];}if (str[i] == s[j + 1]) {j++;}if (j == n) {ans++;j=ne[j];}}return ans;
}
void init(int k)
{for (int i = 1; i < N; i++) {s[i] = 0;}int o = 1;for (int i = 1; i <= k; i++) {for (int j = 0;j <5; j++) {s[o++] = ss[j];}}
}void solve()
{memset(str, 0, sizeof(str));cin >> &str[1];cin >> k;init(k);//cout << s + 1 << endl;int res = kmp();cout << res << endl;
}int main()
{ios::sync_with_stdio(0);cin.tie(0), cout.tie(0);int t;cin >> t;while (t--) {solve();}return 0;
}

E 字母游戏

分数 10

波比和哈丽在玩一个字母游戏，波比给出一个字符串S，要求哈丽按照一定规则，基于该字符串算出一个数字X。

规则是：

（1）求出S的最长重复后缀P（P是S的后缀且在S中出现大于1次，例如yacbacba的最长重复后缀是acba），

（2）求出在S中去除第二长相等前后缀（S中所有相等的前后缀中第2长者，例如abcabcxxxabcabc中最长相等前后缀是abcabc，第二长的相等前后缀则是abc）后剩下的子串Q（例如abcabcxxxabcabc去除第二长相等前后缀后，剩下abcxxxabc）。

则X=P的长度+Q的长度。

注意一个字符串不能称为自己的前缀或后缀。子串Q至少为空串，其长度大于等于0，不能为负数。

请编写程序帮助哈丽根据给定字符串S，根据上述规则计算出数字X。

输入格式:

输入为若干行，每行为一个字符串，包含不超过100000个字母。

输出格式:

输出为若干行，每行一个整数，表示输入字符串所计算出的数字。

输入样例:
abcabcxxxabcabc
xacbacba
abc
aaa
输出样例:
15
12
3
3

题解：

这个题本质上就是对next数组的求解。最长重复后缀就是把字符串倒置后求最大next值。至于第二长的相等前后缀就是把next数组嵌套一次。当然一般的kmp都能用二分加kmp暴力求解。这里也给出暴力做法。注意判断负数值，没判只能拿5分。。（别问我怎么知道的）

法一：二分+kmp（（n+m）logn）

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
char a[N], b[N];
int ne[N];
int ne2[N];
string str;
vector<string>ss;
void init() {for (int i = 1;i < N;i++) {a[i] = 0;ne[i]=0;}for (int i = 1;str[i - 1];i++) {a[i] = str[i - 1];}
}
void fne(int x) {for (int i = 2, j = 0;i <= x;i++) {while (j > 0 && a[i] != a[j + 1]) {j = ne[j];}if (a[i] == a[j + 1]) {j++;}ne[i] = j;}
}
void fne2(int x) {for (int i = 1;ne2[i];i++) {ne2[i] = 0;}for (int i = 2, j = 0;i <= x;i++) {while (j > 0 && b[i] != b[j + 1]) {j = ne2[j];}if (b[i] == b[j + 1]) {j++;}ne2[i] = j;}
}
bool kmp(int x,int y) {if (x <= 0) {return false;}for (int i = 1, j = 0;i <= y-1;i++) {while (j > 0 && a[i] != b[j + 1]) {j = ne2[j];}if (a[i] == b[j + 1]) {j++;}if (j == x) {return true;}}return false;
}
bool find(int x,int y) {for (int i = 1;b[i];i++) {b[i] = 0;}for (int i = 1;a[y - x + i];i++) {b[i] = a[y - x + i];}//cout << b + 1 << endl;fne2(x);if (kmp(x,y)) {return true;}else {return false;}}int main()
{ios::sync_with_stdio(0);cin.tie(0), cout.tie(0);while (cin >> str) {int ans = 0;int n = str.size();init();fne(n);int l = 0, r = n-1;int mid = l+r>>1;int o = 0;while (l <= r) {//cout << mid << endl;if (find(mid,n)) {if (mid > o) {o = mid;}l = mid + 1;}else {r = mid-1;}mid = (l + r )>> 1;}//cout << o << endl;//cout << ne[ne[n]] << endl;ans += o;if (n-2*ne[ne[n]]>0)ans += (n - 2 * ne[ne[n]]);cout << ans << endl;}}

法二：倒置求next数组（On）

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
char str[N];
void fne(int *next,int n,char *ss) {for (int i = 2, j = 0;i <= n;i++) {while (j > 0 && ss[i] != ss[j + 1]) {j = next[j];}if (ss[i] == ss[j + 1]) {j++;}next[i] = j;}
}
void solve()
{int n = strlen(str + 1);int ne[N] ;int ne2[N] ;char s[N] ;for (int i = n;i >= 1;i--) {s[i] = str[n - i + 1];}fne(ne, n, str);fne(ne2, n, s);int max_ne = 0;for (int i = 1;i <= n;i++) {if (max_ne < ne2[i]) {max_ne = ne2[i];}}int res = 0;if (n - 2 * ne[ne[n]] > 0) {res += (n - 2 * ne[ne[n]]);}//cout << max_ne << endl;res += max_ne;cout << res << endl;}int main()
{ios::sync_with_stdio(0);cin.tie(0), cout.tie(0);while (cin >> &str[1]) {solve();}
}

F 小龙猜数字

我们称一个字符串的秩为：该字符串长度减去该字符串的最短相等前后缀的长度。若该字符串不存在相等的前后缀，则其秩为0。

例如：abcabcxabcabc最短相等前后缀为abc，该字符串的秩为10。

Pororo和小龙玩猜字游戏，Pororo给出一个字符串S，小龙需计算S及S中所有前缀子串的秩之和。请编写程序帮助小龙猜数字。

输入格式:

输入为2行，第1行为字符串S的长度，第2行为具体的字符串。字符串长度不超过106。

输出格式:

输出一个整数表示字符串S及其所有前缀的秩之和。

注：结果超出int型变量范围，请使用long long型变量。

输入样例1:
6
ababab
输出样例1:
12
样例1解释:

a的秩为0，ab的秩为0，aba的秩为2，abab的秩为2，ababa的秩为4，ababab的秩为4。

输入样例2:
10
bbcabbabbc
输出样例2:
32

题解：

求最短相等前后缀就是求next数组后依次嵌套。

#include<iostream>
#include<cstring>
using namespace std;
const int N = 1e6 + 10;
char a[N];
int ne[N];
int n;
int main()
{ios::sync_with_stdio(0);cin.tie(0), cout.tie(0);cin >> n;cin >> &a[1];//cout << a+1 << endl;for (int i = 2, j = 0; i <= n; i++) {while (j > 0 && a[i] != a[j + 1]) {j = ne[j];}if (a[i] == a[j + 1]) {j++;}ne[i] = j;}for (int i = 1; i <= n; i++) {if (ne[i] == 0) {continue;}else {if (ne[ne[i]] == 0) {continue;}else {ne[i] = ne[ne[i]];}}}long long ans = 0;for (int i = 1; i <= n; i++) {if (ne[i] == 0) {continue;}else {ans += (i - ne[i]);}}cout << ans;
}