#3108. 「TJOI2019」甲苯先生和大中锋的字符串

Summarize

给定字符串 $s$，求出 $s$ 恰好出现 $k$ 次的子串中长度中出现次数最多的长度数。

$|s|\le 100000$

刚刚学习了后缀自动机，当然要写一篇算法学习啦。

占坑，先咕。

#3095. 「SNOI2019」字符串

Summarize

给出一个长度为 $n$的由小写字母组成的字符串 ，设其中第$i$ 个字符为 $a_i$。设删掉第 $i$个字符之后得到的字符串为$s _i$ ，请按照字典序对 $s_1$,…，$s_n$从小到大输出编号。若两个字符串相等，则认为编号小的字符串字典序更小。

$1 \le n \le 10^5$

感谢@oy的贡献

概述

给定一个文本 $A$ 和一个字符串 $B$ ，我们可以利用 KMP 算法尝试找到并展示 $B$ 在 $A$ 中的所有出现（occurrence）。

题目链接

本题是一道非常漂亮的模拟。只要能理清思路，代码并不会特别复杂。

首先分析题目。解一元一次方程最简单的方法就是移项，把常数移到等号右侧，把一次项系数移到等号左侧，用常数除以系数即为答案。那么在读入字符串的过程中，便可以进行操作。

对于字符串中的数据，我们可以用类似快读的方法读入。然而，要判断这些数据从哪里来，到哪里去，便是本题的关键所在。

对于每个数据，要想清楚地辨别它的身份，我们只需解决三个问题：

1.该数据是正数还是负数？

3.该数据在等号左侧还是在等号右侧？

2.该数据是常数还是系数？

第一个问题看似十分无脑，用一个变量f1来存储符号即可（将f1赋值为1或-1，在读入数据结束时将得到的数据乘以f1）。但需特别注意，在一个表达式的开头（等号左侧和等号右侧的表达式）不会有‘+’、‘-’符号，所以在程序的开头和读入‘=’号是，要将f1赋值为1。

第二个问题也非常简单，可以用变量f2来存储。因为这个问题与移项运算的符号有关，因此也可以将f2赋值为1或-1，并约定在等号左侧时f2为1，在等号右侧时f2为-1。（当然你也可以反着约定）

第三个问题同样不难解决。在读入数据结束后（即读入了一个符号），判断这个符号是运算符还是字母即可。如果是字母，则将得到的数据移到等号右侧，否则将数据移到等号左侧。但是还有一个注意点：如果一个未知数的系数为1，我们会将系数省略。因此在读入数据为0时，我们要将其更改为1。

经过分析，你会发现本题一点也不难实现。其关键在于对数据状态的准确描述。用清晰、简洁的变量描述状态，根据不同的状态采取不同的措施，这便是编程学习的一大基本素养。

代码如下：