一、题目描述
依旧是字符串处理，设A和B是两个字符串。我们要用最少的字符操作次数，将字符串A转换为字符串B。这里所说的字符操作共有三种：
删除一个字符；
插入一个字符；
将一个字符改为另一个字符。 对任给的两个字符串A和B，计算出将字符串A变换为字符串B所用的最少字符操作次数。
输入描述
第一行为字符串A；第二行为字符串B；字符串A和B的长度均小于200。
输出描述
只有一个正整数，为最少字符操作次数。
测试样例
输入
sfdxbqw
gfdgw
输出
4
标准动态规划，关键：找准状态转移方程。这个自己只得了40分。不知道60分是啥问题。
二、题目描述
所给字符串正序和反序连接，形成新串并输出
输入描述
任意字符串（长度<=50）
输出描述
字符串正序和反序连接所成的新字符串
测试样例
输入
123abc
输出
123abccba321
打卡题。reverse+string
三、
题目描述
如果在输入的字符串中，含有 类似于“d-h”或者“4-8”的字串，我们就把它当作一种简写，输出时，用连续递增的字母获数字串替代其中的减号，即，将上面两个子串分别输出为 “defgh”和“45678”。在本题中，我们通过增加一些参数的设置，使字符串的展开更为灵活。具体约定如下：
(1) 遇到下面的情况需要做字符串的展开：在输入的字符串中，出现了减号“-”，减号两侧同为小写字母或同为数字，且按照ASCII码的顺序，减号右边的字符严格大于左边的字符。
(2) 参数p1：展开方式。p1=1时，对于字母子串，填充小写字母；p1=2时，对于字母子串，填充大写字母。这两种情况下数字子串的填充方式相同。p1=3时，不论是字母子串还是数字字串，都用与要填充的字母个数相同的星号“*”来填充。
(3) 参数p2：填充字符的重复个数。p2=k表示同一个字符要连续填充k个。例如，当p2=3时，子串“d-h”应扩展为“deeefffgggh”。减号两边的字符不变。
(4) 参数p3：是否改为逆序：p3=1表示维持原来顺序，p3=2表示采用逆序输出，注意这时候仍然不包括减号两端的字符。例如当p1=1、p2=2、p3=2时，子串“d-h”应扩展为“dggffeeh”。
(5) 如果减号右边的字符恰好是左边字符的后继，只删除中间的减号，例如：“d-e”应输出为“de”，“3-4”应输出为“34”。如果减号右边的字符按照 ASCII码的顺序小于或等于左边字符，输出时，要保留中间的减号，例如：“d-d”应输出为“d-d”，“3-1”应输出为“3-1”。
数据规模和约定
100%的数据满足：1< =p1< =3，1< =p2< =8，1< =p3< =3。字符串长度不超过100
输入描述
输入包括两行： 第1行为用空格隔开的3个正整数，一次表示参数p1，p2，p3。 第2行为一行字符串，仅由数字、小写字母和减号“-”组成。行首和行末均无空格。
输出描述
输出只有一行，为展开后的字符串。
测试样例
输入
121abcs-w1234-9s-4zz
输出
abcsttuuvvw1234556677889s-4zz
复杂模拟，踏下心来做
四、
题目描述
Pear有一个字符串，不过他希望把它切成两段。 这是一个长度为N（<=10^5）的字符串。 Pear希望选择一个位置，把字符串不重复不遗漏地切成两段，长度分别是t和N-t（这两段都必须非空）。
Pear用如下方式评估切割的方案： 定义“正回文子串”为：长度为奇数的回文子串。 设切成的两段字符串中，前一段中有A个不相同的正回文子串，后一段中有B个不相同的非正回文子串，则该方案的得分为A*B。
注意，后一段中的B表示的是：“...非正回文...”，而不是: “...正回文...”。 那么所有的切割方案中，A*B的最大值是多少呢？
输入描述
输入第一行一个正整数N（<=10^5）接下来一行一个字符串，长度为N。该字符串仅包含小写英文字母。
输出描述
一行一个正整数，表示所求的A*B的最大值。
测试样例
输入
10bbaaabcaba
输出
38
类似动规的题。正向遍历 求正回文，反向遍历 求非正回文。数组每个项代表相应位置回文个数，找哪个乘积最大。
关键：时间复杂度如何降低。是求出还所字串吗？还是有技巧的求子串。
五、
题目描述
给出一个非空的正则表达式和一个字符串，求该字符串是否能匹配该正则表达式。
这个正则表达式可能含有：
基本元素：
空串，输入中不体现；
单个小写字母（例如 a ），a 匹配小写字母 a，这里 a 表示小写字母 a。
运算符：
连接（例如 ab），ab 匹配可以表示成一个与 a 匹配的串与一个与 b 匹配的串相连接的串，这里 a 表示一个正则表达式，下同。
或（例如 a|b），a|b 匹配与 a 和 b 中至少一个匹配的串。
闭包（例如 a），a 匹配零个或多个与 a 匹配的串的连接。
正闭包（例如 a+），a+ 匹配一个或多个与 a 匹配的串的连接。
括号（例如 (a)）
其中连接和或是二元运算符，闭包和正闭包是一元运算符。
所有运算符都是左结合的，即同等优先级的运算顺序从左到右。
闭包和正闭包的优先级最高，连接次之，或的优先级最低。
输入描述
多组数据，每组数据两行：
第一行是一个非空正则表达式，保证符合上述定义，但可能出现多余括号。保证不出现空括号。
第二行是一个由小写字母组成的非空字符串。
输出描述
对于每组数据，如果正则表达式能匹配该字符串，输出一行"Yes"，否则输出一行"No"，不含引号。
测试样例
输入
aaaa*aaa+ac*a*baabab*abbba(a|b+)*aaaa(a|b+)*aaababbaa(a|cb+)*aacaa(a|cb+)*aacbbbaacbaa(a|cb+)*aacbbbaacb((a*))aa
输出
NoYesYesYesNoYesYesNoYesNoYes
网友评论