字符串|【codeforces 576D】LCS Again 字符串|codeforces

给一个串，问有多少和它长度相同的串，使得LCS为l - 1。
【字符串|【codeforces 576D】LCS Again】

#include #include #include #include #include #define Rep(i, x, y) for (int i = x; i <= y; i ++) #define Dwn(i, x, y) for (int i = x; i >= y; i --) #define RepE(i, x) for(int i = pos[x]; i; i = g[i].nex) using namespace std; typedef long long LL; const int N = 100005; int n, m, p, q, s1[N], s2[N]; char s[N]; LL ans; int main() { scanf ("%d%d", &n, &m); scanf ("%s", s + 1); ans = n * (m - 1); Rep(i, 1, n - 1) { s1[i] = s1[i - 1] + (s[i] != s[i + 1]); ans += s1[i] * (m - 1); } Dwn(i, n, 2) { s2[i] = s2[i + 1] + (s[i] != s[i - 1]); ans += s2[i] * (m - 1); } Rep(i, 1, n - 1) { p = max(0, p - 2); while (i + p + 2 <= n && s[i + p] == s[i + p + 2]) p ++; if (s[i] != s[i + 1]) ans -= p + 1; swap(p, q); } printf("%I64d\n", ans); return 0; }

字符串|【codeforces 576D】LCS Again

推荐阅读

2018世界杯西班牙对摩洛哥哪个厉害西班牙对摩洛哥预测结果

做了核酸检测健康码什么时候显示

说爱你蔡依林mp3下载如何评价蔡依林唱的说爱你，说爱你周杰伦

吉林有哪些特色水果吉林的水果

行车记录仪小的好还是大的好 2021年口碑最好的行车记录仪

东床快婿原本指的是什么成语东床快婿最初指的是谁

玩英雄联盟电脑最低配置要求玩英雄联盟的电脑最低配置是多少

辛辰和他的辛辰身世公开了没

孕妇是否可以吃石榴

常州轻工学院几个食堂常州轻工职业技术学院怎么样

ip前所未有的超高性价比？苹果iPad SE平板曝光

酷狗音乐如何制作歌词,酷狗歌词制作有报酬么

实现抵押权申请书

年轻人头晕晕沉沉是怎么回事为什么头有点晕

高德地图如何参加双11集能量_收集能量详细图文教程

2016office永久激活码教程正版office2016激活码多少钱

画圣诞树的软件app，想问一下这个是那个手机指绘软件谢谢大家了

华为荣耀9怎么样好用吗

国产手办真的很烂吗为什么叫手办

大学生消费调查报告范文精选6篇