计算机23级数据结构上机实验（第1-2周）

A 括号匹配（进阶版）

编写程序检查给定字符串中包含的括号是否正确匹配，本题中的括号有{ }、[ ]、( )、< >四种。另外再加上一个新的约束条件：当有多种括号嵌套时，嵌套的顺序应为{ → [ → ( → <，即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

解题思路：

1. 栈的使用：
   • 当遇到左括号时，入栈。
   • 当遇到右括号时，检查栈顶是否有匹配的左括号，如果有则出栈；如果没有，则匹配失败。
2. 嵌套顺序约束：
   • 在遇到左括号时，检查当前左括号的优先级是否低于栈顶括号的优先级（根据嵌套规则设定优先级 {=4, [=3, (=2, <=1）。
   • 核心即为各个符号设置相应数值当作优先级
   • 如果优先级不满足嵌套规则，则匹配失败。
3. 相同类型嵌套约束：
   • 在遇到左括号时，检查栈顶是否为相同类型的括号。如果是，则匹配失败。
4. 最终检查：
   • 字符串遍历结束后，若栈中仍有剩余的左括号，则匹配失败。
   • 若栈为空，则匹配成功。

#include<iostream>
using namespace std;

// 定义一个字符数组作为栈，用于存储左括号
char stack[1001];
// 定义一个变量top，用于记录栈顶的位置
int top;

// 判断字符是否为左括号
bool isleft(char a)
{
    // 定义一个字符串包含所有左括号
    string n = "<([{";
    bool flag = false;
    // 遍历字符串，检查字符是否为左括号
    for (int i = 0; i < 4; i++)
    {
        if (a == n[i])flag = true;  
    }
    return flag;
}

// 判断字符是否为右括号
bool isright(char a)
{
    // 定义一个字符串包含所有右括号
    string n = ">)]}";
    bool flag = false;
    // 遍历字符串，检查字符是否为右括号
    for (int i = 0; i < 4; i++)
    {
        if (a == n[i])flag = true;
    }
    return flag;
}

// 获取括号的优先级
int precedent(char a)
{
    // 根据括号类型返回对应的优先级
    if (a == '<')return 1;
    else if (a == '(')return 2;
    else if (a == '[')return 3;
    else if (a == '{')return 4;
}

// 判断两个括号是否匹配
bool match(char a, char b)
{
    // 定义一个字符串包含所有括号的匹配对
    string v = "<>()[]{}";
    int flag = false;
    // 遍历字符串，检查括号是否匹配
    for (int i = 0; i < 8; i = i + 2)
    {
        if (a == v[i] && b == v[i + 1])
        {
            flag = true;
        }
    }
    return flag;
}

// 检查括号是否匹配的函数
void address(string v)
{
    // 遍历输入的字符串
    for (int i = 0; i < v.size(); i++)
    {
        //判断是否为左右括号
        bool flag1 = isleft(v[i]), flag2 = isright(v[i]);
        // 如果是左括号
        if (flag1||flag2)
        {
            // 如果栈为空，直接压栈
            if (top == 0)
            {
                stack[top++] = v[i];
            }
            // 如果是左括号
            else if (flag1)
            {
                // 如果栈顶元素优先级小于等于当前左括号，嵌套失败
                if (precedent(stack[top - 1]) <= precedent(v[i]))
                {
                    cout << "Fail" << endl;
                    return;
                }
                else//继续压栈
                {
                    stack[top++] = v[i];
                }
            }
            // 如果是右括号
            else 
            {
                //判断栈空
                if(top==0||!match(stack[top - 1], v[i]))
                {
                    cout << "Fail" << endl;
                    return;
                }
                // 如果栈顶元素与当前右括号匹配，出栈
                else (match(stack[top - 1], v[i]))
                {
                    top--;
                }
            }
        }
    }
    // 如果栈不为空，说明有未匹配的左括号，输出失败
    if (top != 0)
    {
        cout << "Fail" << endl;
        return;
    }
    // 如果所有括号都匹配，输出成功
    cout << "Match" << endl;
    return;
}

// 主函数
int main()
{
    int n;
    // 输入测试用例的数量
    std::cin >> n;
    // 对每个测试用例进行处理
    for (int i = 0; i < n; i++)
    {
        top = 0;
        string v;
        cin >> v;
        address(v);
    }
}

B 调皮的哈利

贝蒂是个打字高手，打字时有不看屏幕的习惯。在一次贝蒂打字时，调皮的哈利常常趁贝蒂不注意按下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:

tnopqefghiabcdjklm

解题思路

链表模拟输入操作：

• 每个字符存储为一个节点。
• 光标位置对应链表的一个指针now。
• 按键对应不同的链表操作，如{、}修改now的位置，<、>调整光标，#删除节点。
• 核心为使用双向链表，减少前移和删除操作的遍历时间，避免超时

实现按键功能：

• { (Home键)：将光标now移到头节点。
• } (End键)：将光标now移到尾节点。
• < (左键)：将光标now移到前一个节点（如果存在）。
• > (右键)：将光标now移到下一个节点（如果存在）。
• # (退格键)：删除光标左侧的节点。
• 其他字符：在光标后插入一个新节点，并将光标移动到新节点。

构造最终字符串：

• 遍历链表，从头节点开始依次将每个节点的字符拼接成结果字符串。

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

// 定义双向链表节点类
class Listnode
{
public:
    char data;           // 节点存储的字符
    Listnode* next;      // 指向下一个节点的指针
    Listnode* pre;       // 指向上一个节点的指针

    Listnode() = default;  // 默认构造函数

    // 带参数构造函数，用于初始化节点数据
    Listnode(char a) : data(a), next(nullptr), pre(nullptr){ }
};

// 定义双向链表类
class List
{
public:
    Listnode* head;  // 链表的头节点
    Listnode* tail;  // 链表的尾节点
    Listnode* now;   // 当前光标所在的节点

    // 构造函数，初始化头节点
    List()
    {
        head = new Listnode();  // 初始化头节点
        tail = head;            // 初始时尾节点与头节点相同
        now = head;             // 光标也位于头节点
    }

    // 删除当前光标所在的节点
    void deletenode()
    {
        if (now == head)  // 如果光标在头节点，不删除
        {
            return;
        }

        Listnode* p = now;           // 保存当前光标位置的节点
        now->pre->next = now->next;  // 调整前后节点的链接关系

        if (now->next)               // 如果当前节点有后继节点
        {
            now->next->pre = now->pre;  // 更新后继节点的前指针
        }

        if (now == tail)             // 如果删除节点是尾节点
        {
            tail = now->pre;         // 更新尾节点为前一个节点
        }
        now = now->pre;              // 光标向左移动

        delete p;                    // 释放被删除节点的内存
    }

    // 在当前光标位置插入字符
    void Insert(char a)
    {
        Listnode* p = new Listnode(a);  // 创建新节点

        if (now->next)                 // 如果当前节点有后继节点
        {
            now->next->pre = p;        // 更新后继节点的前指针
            p->next = now->next;       // 新节点的后继指向当前节点的后继
        }

        now->next = p;                 // 当前节点的后继指向新节点
        p->pre = now;                  // 新节点的前驱指向当前节点

        if (now == tail)               // 如果当前节点是尾节点
        {
            tail = p;                  // 更新尾节点为新插入的节点
        }
        now = p;                       // 光标移动到新插入的节点
    }

    // 光标向左移动
    void left()
    {
        if (now == head)  // 如果光标已经在头节点，不移动
        {
            return;
        }

        now = now->pre;  // 光标向左移动一位
    }

    // 光标向右移动
    void right()
    {
        if (now == tail)  // 如果光标已经在尾节点，不移动
        {
            return;
        }

        now = now->next;  // 光标向右移动一位
    }

    // 光标移动到头节点
    void Home()
    {
        now = head;
    }

    // 光标移动到尾节点
    void End()
    {
        now = tail;
    }
};

int main()
{
    string n;               // 用于存储输入字符串
    getline(cin, n);        // 读取整行输入
    List list;              // 初始化一个双向链表

    // 遍历输入字符串
    for (int i = 0; i < n.size(); i++)
    {
        switch (n[i])  // 根据字符类型执行不同的操作
        {
        case '{':         // '{' 表示光标移动到文本开头
            list.Home();
            break;
        case '}':         // '}' 表示光标移动到文本末尾
            list.End();
            break;
        case '<':         // '<' 表示光标向左移动
            list.left();
            break;
        case '>':         // '>' 表示光标向右移动
            list.right();
            break;
        case '#':         // '#' 表示删除光标左侧的字符
            list.deletenode();
            break;
        default:          // 其他字符表示插入
            list.Insert(n[i]);
            break;
        }
    }

    // 遍历链表并输出结果
    auto p = list.head->next;  // 从头节点的下一个节点开始
    while (p)
    {
        cout << p->data;       // 输出当前节点的数据
        p = p->next;           // 移动到下一个节点
    }

    return 0;  // 程序结束
}

C 表达式求值

给定一个中缀表达式，请编写程序计算该表达式的值。表达式包含+、-、、/、^、(、)，所有运算均为二元运算，操作数均为正整数，但可能不止一位，不超过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. 中缀表达式求值方法：

   • 栈的使用：运算符栈和操作数栈分别保存当前解析的运算符和数字，遇到操作时根据优先级规则计算。
   • 注意栈顶指针指向最后一个元素还是下一个存放位置
   • 运算符优先级：根据优先级处理运算符，保证表达式按正确的计算顺序进行。依旧转变运算符为数值进行优先级比较
   • 括号处理：( 和 ) 的出现会打破默认的优先级规则，需要特别处理括号内的表达式。

2. 操作数的解析：

   • 表达式中可能包含多位数，需要从当前字符开始连续读取数字，直到遇到非数字字符。(重点)
   • 使用字符减 '0' 的方法将字符转换为整数。

   if (!isop(exp[i])) {
               // 如果当前字符不是运算符，则解析整个数字
               int num = exp[i] - '0'; // 将字符转换为对应的整数
               // 继续读取后续的数字字符，直到遇到运算符或括号
               //注意边界判断（i + 1 < exp.size()）
               while (!isop(exp[i + 1]) && i + 1 < exp.size()) {
                   int p = exp[++i] - '0';
                   num = num * 10 + p;
               }
               numst[ntop++] = num; // 将解析的数字压入数字栈
           }
   

1. 特殊情况处理：

   • 除数为 0：立即返回 INVALID，避免错误的计算，使用全局变量记录非法状态。
   • 幂运算的实现：自行实现一个快速幂函数，用来计算指数，使用快速幂不然会超时。

   //计算a^b
   auto Pow = [&](int a, int b) -> int {
       //特判
       if(a!=0&&b==0)return 1;
       int res = 1; // 初始化结果为1
       while (b > 0) { // 当指数b大于0时循环
           if (b & 1) // 如果b的当前最低位为1
               res = res * a; // 将当前底数a乘到结果res上
           a = a * a; // 底数平方，即翻倍，同时指数除以二
           b = b >> 1; // 指数右移一位，相当于将b整除2
       }
       return res; // 返回最终结果
   };
   

   • 多行输入：每行一个表达式，逐行解析并求值。

2. 具体实现的逻辑：

   • 数字栈：保存操作数，遇到运算符时弹出两个数进行计算。
   • 运算符栈：保存运算符，遇到优先级较低的运算符时，弹出并计算栈顶的运算符。
   • 最终结果：在所有字符解析完后，依次计算剩余栈中的运算符，得到最终结果。

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

// 判断字符是否为运算符或者括号
bool isop(char c) {
    // 定义一个字符串包含所有支持的运算符和括号
    string v = "+-*/^()"; 
    bool flag = false;
    // 遍历字符串，检查传入的字符是否为运算符或括号
    for (auto i : v) {
        if (c == i)
            flag = true;
    }
    return flag;
}

// 获取运算符的优先级
int precedence(char c) {
    // 根据运算符返回其优先级，优先级数字越大，优先级越高
    if (c == '+' || c == '-') return 1; // 加减优先级最低
    else if (c == '/' || c == '*' || c == '%') return 2; // 乘除和取模优先级次之
    else if (c == '^') return 3; // 幂运算优先级最高
    else return int(false); // 如果不是运算符，返回false
}

bool flagvalid = true; // 用于标记计算是否有效，如果遇到错误（如除以零），则设置为false

// 计算两个数和运算符的结果
int calculate(int left, int right, char oper) {
    // 如果是除法且除数为0，则输出错误信息并设置计算无效
    if (oper == '/' && right == 0) {
        cout << "INVALID" << endl;
        flagvalid = false;
        return 0;
    }

    // 快速幂函数，用于计算幂运算
    auto Pow = [&](int a, int b) -> int {
        int res = 1;
        while (b > 0) {
            if (b & 1) // 如果指数的当前位为1，则乘以底数
                res = res * a;
            a = a * a; // 底数平方
            b = b >> 1; // 指数右移一位，相当于除以2
        }
        return res;
    };

    // 根据运算符计算结果
    switch (oper) {
    case '+':
        return left + right;
    case '-':
        return left - right;
    case '*':
        return left * right;
    case '/':
        return left / right;
    case '%':
        return left % right;
    case '^':
        return Pow(left, right); // 调用快速幂函数计算幂
    default:
        break;
    }
}

char opst[1001]; // 运算符栈，用于存储运算符和括号
int numst[1001]; // 数字栈，用于存储操作数
int otop; // 运算符栈顶指针
int ntop; // 数字栈顶指针

// 解析和计算表达式的函数
int address(string exp) {
    flagvalid = true; // 重置计算有效标记
    otop = 0; // 初始化运算符栈顶指针
    ntop = 0; // 初始化数字栈顶指针

    // 遍历表达式中的每个字符
    for (int i = 0; i < exp.size(); i++) {
        if (exp[i] == ' ') {
            continue; // 忽略空格！！！
        } else if (!isop(exp[i])) {
            // 如果当前字符不是运算符，则解析整个数字
            int num = exp[i] - '0'; // 将字符转换为对应的整数
            // 继续读取后续的数字字符，直到遇到运算符或括号
            //注意边界判断（i + 1 < exp.size()）
            while (!isop(exp[i + 1]) && i + 1 < exp.size()) {
                int p = exp[++i] - '0';
                num = num * 10 + p;
            }
            numst[ntop++] = num; // 将解析的数字压入数字栈
        } else if (exp[i] == '(') {
            // 遇到左括号，直接压入运算符栈
            opst[otop++] = exp[i];
        } else if (exp[i] == ')') {
            // 遇到右括号，计算括号内的表达式
            while (opst[otop - 1] != '(') {
                //因为表达式一定合法所以不需要判断栈是否为空
                int right = numst[--ntop]; // 弹出数字栈的顶部两个元素作为操作数
                int left = numst[--ntop];
                char op = opst[--otop]; // 弹出运算符栈的顶部元素作为运算符
                numst[ntop++] = calculate(left, right, op); // 计算结果并压回数字栈
            }
            otop--; // 弹出左括号
        } else {
            // 遇到运算符，根据优先级处理
            if (otop == 0 || opst[otop - 1] == '(') {
                // 如果运算符栈为空或栈顶为左括号，直接压入运算符
                opst[otop++] = exp[i];
            } else if (precedence(opst[otop - 1]) >= precedence(exp[i])) {
                // 如果栈顶运算符的优先级不小于当前运算符，计算栈顶运算符的表达式
                //根据栈的先进后出，所以先出栈的右操作数
                int right = numst[--ntop];
                int left = numst[--ntop];
                char op = opst[--otop];
                numst[ntop++] = calculate(left, right, op);
                opst[otop++] = exp[i];
            } else {
                // 否则，直接压入当前运算符
                opst[otop++] = exp[i];
            }
        }

        // 如果计算无效，提前返回
        if (!flagvalid) return 0;
    }

    // 处理完所有运算符后，计算剩余的表达式
    while (otop != 0) {
        int right = numst[--ntop];
        int left = numst[--ntop];
        char op = opst[--otop];
        numst[ntop++] = calculate(left, right, op);

        // 如果计算无效，提前返回
        if (!flagvalid) return 0;
    }

    // 返回最终结果
    return numst[--ntop];
}

int main() {
    string exp;
    // 循环读取每一行表达式，直到输入结束
    while (getline(cin, exp)) {
        int p = address(exp);
        if (flagvalid) {
            cout << p << endl; // 如果计算有效，输出结果
        }
    }

    // 暂停，等待用户操作，以便查看输出结果
    system("Pause");
    return 0;
}

• 以下三题都利用了next数组的意义，
• 所以核心就是求出next数组

// 计算 next 数组，用于 KMP 算法
void getnext(string T, int* next) {
    int l = T.size(); // 获取模式串 T 的长度
    next[0] = -1; // next 数组的第一个元素初始化为 -1
    int k = -1; // 初始化 k 为 -1，k 用于表示当前比较的前一个字符的位置
    int j = 0; // j 用于遍历 T
    while (j < l-1) //根据具体问题决定是否算出next[l-1],同时注意next的长度
    { // 遍历 T，直到倒数第二个字符
        if (k == -1 || T[k] == T[j]) { // 如果 k 为 -1 或当前字符与前一个字符相同
            k++; // 移动 k 指针
            j++; // 移动 j 指针
            next[j] = k; // 更新 next 数组
        } else { // 如果当前字符与前一个字符不同
            k = next[k]; // 移动 k 到 next[k] 指定的位置
        }
    }
}

D EDG

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

解题思路

核心：求next数组

1. 模式串生成：

   • 基本模式串是 "edgnb"，长度为 5。
   • 若需要匹配连续 k 个 "edgnb"，只需重复模式串 k 次，即模式串变为 "edgnb...edgnb"（k 个 "edgnb"）。
   • 并根据KMPnext数组的定义优化为除了第一次k个edgnb,后面只需从前面匹配成功的第k-1个edgnb开始匹配,即指针j后移

   if (j == tl) { // 如果 j 到达了 T 的末尾
               num++; // 增加计数
               j = j - 5; // 将 j 移动到 T 的开头，因为 T 重复了 k 次，所以移动 -tl 位置
           }
   

1. 使用 KMP 算法：

   • 通过 KMP 算法，可以高效找到主串中模式串的所有匹配位置。
   • KMP 的核心是利用 next 数组 记录部分匹配信息，避免重复比较，从而提升匹配效率。

2. 优化重复检测：

   • 模式串的重复特性在 KMP 算法中天然适合处理。
   • 在每次完整匹配模式串后，可以直接跳过模式串的长度继续匹配下一个位置。

3. 输出匹配次数：

   • 遍历每组测试用例，对每个字符串和 k 值，依次使用上述方法计算匹配次数并输出。

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

// 计算 next 数组，用于 KMP 算法
void getnext(string T, int* next)
{
    int l = T.size(); // 获取模式串 T 的长度
    next[0] = -1;     // 初始化 next 数组的第一个值为 -1
    int k = -1;       // k 表示当前匹配的位置
    int j = 0;        // j 用于遍历模式串 T

    // 构建 next 数组
    while (j < l - 1)
    {
        if (k == -1 || T[k] == T[j]) // 如果匹配成功或回溯到起点
        {
            k++;         // k 向前移动
            j++;         // j 向前移动
            next[j] = k; // 记录匹配的长度
        }
        else
        {
            k = next[k]; // 如果匹配失败，回溯到上一个匹配位置
        }
    }
}

// KMP 算法用于匹配字符串
int KMP(string S, string T, int k)
{
    int num = 0;           // 用于统计匹配次数
    int sl = S.size();     // 主串 S 的长度
    int i = 0, j = 0;      // i 遍历主串，j 遍历模式串

    // 根据 k 值重复生成新的模式串
    string v = T;          // 保存原始模式串
    for (int i = 1; i < k; i++)
    {
        T = T + v;         // 重复拼接 k 次
    }
    int tl = T.size();     // 模式串的总长度

    // 构造 next 数组
    int* next = new int[tl];
    getnext(T, next);

    // 匹配主串 S
    while (i < sl)
    {
        if (j == tl)       // 如果模式串全部匹配成功
        {
            num++;         // 匹配计数加一
            j = j - 5;     // 后移一个完整的 "edgnb" 长度
        }

        if (j == -1 || S[i] == T[j]) // 如果当前字符匹配成功，或 j 回溯到起点
        {
            i++;           // 主串指针移动
            j++;           // 模式串指针移动
        }
        else
        {
            j = next[j];   // 根据 next 数组回溯
        }
    }

    if (j == tl)           // 处理最后一次完整匹配
    {
        num++;
    }

    delete[] next;         // 释放 next 数组的内存
    return num;            // 返回匹配次数
}

// 主函数
int main()
{
    string S, T;
    T = "edgnb";           // 初始化模式串为 "edgnb"

    int n;                 // 测试用例数量
    cin >> n;              // 读取测试用例数量
    for (int i = 0; i < n; i++)
    {
        int k;             // 模式串需要重复的次数
        cin >> S >> k;     // 读取主串 S 和重复次数 k
        cout << KMP(S, T, k) << endl; // 输出匹配次数
    }
}

E 字母游戏

波比和哈丽在玩一个字母游戏，波比给出一个字符串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

解题思路

1. 求字符串的最长重复后缀 P：

   • 一个后缀 P 被定义为“既是字符串的后缀，也是字符串中的某个子串”。
   • 使用字符串翻转后，再利用 KMP 算法的 next 数组即可计算最长重复后缀的长度。因为翻转后，最长重复前缀的长度即为原字符串的最长重复后缀的长度。

2. 求去除第二长相等前后缀后的子串 Q：

   • next 数组不仅记录了每个位置的最长相等前后缀长度，也可以用来找到次长的相等前后缀长度。
   • 原字符串去掉次长相等前后缀后，剩余的部分即为 Q。
   • 注意下界为0

3. 计算最终结果 X：

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

4. 为何 next 需要多一位

   1. 在 KMP 中的常规用法：
      • next[j] 对应的是子串 T[0...j-1]。
      • KMP 的匹配过程中并不需要计算整个字符串的前后缀，只需用到部分 next 信息，因此不需要额外一位。
   2. 本题的需求：
      • 这里要求的是 整个字符串的最大相等前后缀 和 次长的相等前后缀。
      • 为了得到完整的字符串信息，需要扩展 next 数组的长度为 l+1，并在 next[length] 中存储整个字符串的最大相等前后缀。

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

// 计算翻转字符串的next 数组，并返回最大相等前后缀的长度，即最长重复后缀P
int getnext_and_max(string T) {
    int l = T.size(); // 获取字符串 T 的长度
    int* next = new int[l+1];// 创建 next 数组，大小为 l+1，因为next数组中next[j]的意义是字符串中T[j]前的子串的最大相等前后缀，KMP匹配不需要整个字符串的最大相等前后缀，但这题需要，因此多一位给整个字符串

    next[0] = -1; // 初始化 next 数组的第一个元素为 -1

    int max = next[0]; // 初始化最大相等前后缀长度为 -1

    int k = -1; // 初始化 k 为 -1，k 用于表示当前比较的前一个字符的位置
    int j = 0; // j 用于遍历 T，计算最大相等前后缀
    while (j < T.size()) { // 遍历 T （j<T.size() / j<=T.size()-1)
        if (k == -1 || T[j] == T[k]) { // 如果 k 为 -1 或当前字符与前一个字符相同
            ++k; // 移动 k 指针
            ++j; // 移动 j 指针
            next[j] = k; // 更新 next 数组
            if (max < next[j]) max = next[j]; // 更新最大相等前后缀长度
        } else { // 如果当前字符与前一个字符不同
            k = next[k]; // 移动 k 到 next[k] 指定的位置
        }
    }
    delete[] next; // 释放 next 数组的内存

    return max; // 返回最大相等前后缀长度
}

// 计算 next 数组
int* getnext(string T) {
    int l = T.size(); // 获取字符串 T 的长度
    int* next = new int[l + 1]; // 创建 next 数组，大小为 l+1，因为next数组中next[j]的意义是字符串中T[j]前的子串的最大相等前后缀，KMP匹配不需要整个字符串的最大相等前后缀，但这题需要，因此多一位给整个字符串

    next[0] = -1; // 初始化 next 数组的第一个元素为 -1

    int k = -1; // 初始化 k 为 -1，k 用于表示当前比较的前一个字符的位置
    int j = 0; // j 用于遍历 T，计算最大相等前后缀
    while (j < T.size()) { // 遍历 T
        if (k == -1 || T[j] == T[k]) { // 如果 k 为 -1 或当前字符与前一个字符相同
            ++k; // 移动 k 指针
            ++j; // 移动 j 指针
            next[j] = k; // 更新 next 数组
        } else { // 如果当前字符与前一个字符不同
            k = next[k]; // 移动 k 到 next[k] 指定的位置
        }
    }
    return next; // 返回 next 数组
}

// 翻转字符串
string re(string a) {
    int v = a.size(); // 获取字符串 a 的长度
    for (int i = 0; i < a.size()/2; i++) { // 遍历字符串的前半部分
        int temp = a[i]; // 临时变量存储字符
        a[i] = a[v - 1 - i]; // 交换字符
        a[v - 1 - i] = temp; // 交换字符
    }
    return a; // 返回翻转后的字符串
}
//可以用reverse(a.begin(), a.end());

// 计算翻转后的字符串的最大相等前后缀长度
int longback(string T) {
    int tl = T.size(); // 获取字符串 T 的长度
    string e = re(T); // 翻转字符串 T
    return getnext_and_max(e); // 计算翻转后的字符串的最大相等前后缀长度
}

// 计算第二个最长的前后缀长度
int second_preandback(string T) {
    int* next; // 创建 next 数组
    next = getnext(T); // 计算 next 数组
    int tl = T.size(); // 获取字符串 T 的长度
    if (next[tl] > 0) { // 如果 next 数组的最后一个元素大于 0
        return next[next[tl]]; // 返回第二个最长的前后缀长度
    } else return 0; // 如果没有第二个最长的前后缀，返回 0
}

int main() {
    string v; // 读取字符串
    while (cin >> v) { // 循环读取字符串
        int P = longback(v); // 计算最长的前后缀长度
        int l = second_preandback(v); // 计算第二个最长的前后缀长度
        int Q = v.size(); // 获取字符串 v 的长度
        if (2 * l <= Q) { // 如果两个最长的前后缀长度之和小于等于字符串长度
            Q = Q - 2 * l; // 计算剩余长度
        } else { // 如果两个最长的前后缀长度之和大于字符串长度
            Q = 0; // 剩余长度为 0
        }

        cout << P + Q << endl; // 输出最长和第二长的前后缀长度之和
    }
}

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

解题的核心

高效计算所有前缀子串的秩 是本题的重点。

利用 KMP 的 next 数组

• next[i] 的含义：子串 S[0...i-1] 的最大相等前后缀的长度。
• 我们需要进一步从 next[i] 推导出 最短相等前后缀的长度。

关键点：最短相等前后缀

• 对于 next[i]，如果它的值是 k，这意味着子串 S[0...i-1] 的前缀和后缀有一个公共部分，长度为 k。
• 最短相等前后缀 是指在 k 的基础上，去递归检查 next[k]，直到找到最短的那个相等前后缀。
• 利用动态规划减少递归的时间，即从前往后更新next数组
• next[j]=(next[next[j]] != 0)? next[next[j]] : next[j]

计算公式

1. 每个前缀子串的秩： rank[i]=i−最短相等前后缀的长度
2. 总和为所有前缀子串的秩之和。

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

// 计算 next 数组，用于后续计算排名（rank）
int* getnext(string T) {
    int l = T.size(); // 获取字符串 T 的长度
    int* next = new int[l + 1]; // 创建 next 数组，大小为 l+1，多出一个位置存储哨兵值 -1

    next[0] = -1; // 初始化 next 数组的第一个元素为 -1

    int k = -1; // 初始化 k 为 -1，k 用于表示当前比较的前一个字符的位置
    int j = 0; // j 用于遍历 T，计算最大相等前后缀
    while (j < T.size()) { // 遍历 T
        if (k == -1 || T[j] == T[k]) { // 如果 k 为 -1 或当前字符与前一个字符相同
            ++k; // 移动 k 指针
            ++j; // 移动 j 指针
            next[j] = k; // 更新 next 数组
        } else { // 如果当前字符与前一个字符不同
            k = next[k]; // 移动 k 到 next[k] 指定的位置
        }
    }

    return next; // 返回 next 数组
}

// 计算所有排名（rank）之和
long long getallrank(int next[], int n) {
    long long all = 0; // 初始化排名之和为 0
    for (int i = 1; i <= n; i++) {
        int rank = i; // 初始化排名为当前位置 i
        if (next[i] == 0) {
            rank = 0; // 如果 next[i] 为 0，排名为 0
        } else {//核心！！！
            int k = next[next[i]]; // 计算 next[next[i]] 的值
            if (k > 0) next[i] = k; // 如果 k 大于 0，更新 next[i]
            rank -= next[i]; // 计算排名
        }
        all += rank; // 累加排名
    }
    return all; // 返回排名之和
}

int main() {
    long long n; // 读取长整型数 n
    string v; // 读取字符串 v
    cin >> n >> v; // 输入

    int* next = getnext(v); // 计算 next 数组
    cout << getallrank(next, n) << endl; // 输出排名之和

    //system("Pause"); // 暂停，等待用户操作，已注释掉
}