首页 > 其他 > 详细

Codeforces 954I Yet Another String Matching Problem(并查集 + FFT)

时间:2018-04-09 20:37:12      阅读:371      评论:0      收藏:0      [点我收藏+]

题目链接  Educational Codeforces Round 40  Problem I

题意  定义两个长度相等的字符串之间的距离为:

    把两个字符串中所有同一种字符变成另外一种,使得两个字符串相等所需要操作的次数的最小值。

    求$s$中每一个长度为$t$的长度的连续子串与$t$的距离。字符集为小写字母$a$到$f$

 

首先解决求两个长度相等的字符串之间的距离这个问题。

$s$和$t$相同位上的字母连一条无向边,最后的答案是$s$和$t$中所有出现过的字符的个数减去这个无向图的连通块个数。

 

Codeforces 954I Yet Another String Matching Problem(并查集 + FFT)

原文:https://www.cnblogs.com/cxhscst2/p/8762073.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!