字符串|【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

推荐阅读

永嘉风光永嘉哪里好玩

劳动是意思相近的词吗快乐是意思相近的词语吗

没开封茶叶会不会过期

迷你世界手机版怎么去竹桃林桃林地形码迷你世界分享

画图工具怎么手绘一款简笔画蛋糕？画图工具手绘简笔画蛋糕的方法

win10epic遭遇了网络连接问题解决方法

荷包蛋面条怎么做荷包蛋面条怎么做视频

4s店样品车可以买吗现在 4s店样品车可以买吗

汽车新四化是什么谈谈汽车新四化

聪明的梅花鹿告诉了我们什么道理一只梅花鹿告诉我们什么道理

周公解梦梦见骨灰盒是什么意思梦见骨灰盒好不好

皮肤瘙痒冷敷多久最好

毛衣可以和其他衣服一起用洗衣机洗吗

十一岁的男孩怎么教育

win101909声卡没声音解决方法

3dmax怎么做雪景关于3DMAX制作雪景的详细操作

品牌规划的流程

手机里库乐队删了怎么办手机库乐队没了怎么办

准备从事棋牌游戏人员必读

审议不通过怎么写会议纪要如何写会议纪要