苟且的狮子的博客

[SDOI2016]生成魔咒

后缀数组、set、离散题解：分析：首先让我们看看这一题要求的是什么。每一个索引到最左端能构成的魔咒的数量。看到这里我们应该能反应过来。抓住不变的东西，最左端是始终不变的。如果我们把字符串reverse一下，那么求的就是每一个后缀的魔咒数量了！！！很明显的线索那么就让我们来思考一下反转后字...

[HAOI2016]找相同字符

后缀数组、单调栈题意：分析：题意十分的清爽，但是却让人一筹莫仔细地分析我们便会发现，我们可以利用后缀数组来进行求解。我们比对s1和s2的每一个后缀。然后计算其和就可以了。对不对，其实题目中的也就是这个意思而已罢了。很简单，我们可以这样构造一个字符串s1+'$'+s2，我们求其SA和rmq。...

优秀的拆分

后缀数组、重复子串、回文子串题意：分析：刚拿到这题我是崩溃的，这可咋求啊？！AABB的，太吓人了！！然后我仔细看了看，其实问题的关键在于如何判断一个连续的AA串！！如果我们能够计算出哪里有AA串就好了。比如：a[i]记录了一索引i结尾的AA串有多少个b[i]记录了一索引i开始的AA串有多...

[TJOI2017]DNA

后缀数组，枚举和暴力这是我的第一道真正意义上的后缀数组题！！！！！而且1A。祝贺！！！！！鸣炮！！！！！题意：分析：我的想法很简单，就是枚举。我想对s1从头到尾枚举每一个长度为s1.size()的子串。记s2得长度为m。枚举[0,m)、[1,m+1)、[2,m+2)......看枚举的字...