HDU 5769 Substring (后缀数组)

HDU 5769 Substring (后缀数组)

题目链接:点我~~ 题意:输入一个字符,一个串,问你输入的串中的子串中有多少个包含这个字符。 思路:不重复子串的个数是len-sa[i]-height[i],但是现在有这样的情况,就是字符是c,而sa[i]是dddcddd,那么它能贡献的值就是len-max((sa[i]+height[i]),c的位置),因为若sa[i]+height[i]的值大于c的位置...
09月24日 1,726
HDU 5880 Family View (AC自动机)

HDU 5880 Family View (AC自动机)

题目链接:点我~~ 题意:敏感词屏蔽,给一堆敏感词,给一段文本,要求把文本中所有的敏感词用*代替。 思路:对敏感词建出AC自动机,在AC自动机上跑文本,可以得到每个前缀的最长匹配后缀,再将每一匹配到的段标记,最后再扫一遍输出。 #include <bits/stdc++.h> using namespace std; typedef long...
09月22日 1,831
  1. .01 4:06
  2. .02 1:47
  3. .03 3:39
  4. .04 1:40