字符串

题意：~ 思路： #include <bits/stdc++.h> using namespace std; typedef long long LL; template <class T> inline bool scan_d(T &ret) {char c; int sgn;if(c=getchar(),c==EOF...

题意：~ 思路： #include <bits/stdc++.h> using namespace std; const int N = 400050; struct Trie { int next[N][26]; int root, L; int num[26]; int newnode...

题目链接：点我~~ 题意：给定序列a、序列b和一个整数p，要求出有多少个q使得b1,b2,…,bm恰好是aq,aq+p,…,aq+(m−1)p。 思路：将a按照MODp拆成若干个串，分别做一次 KMP. #include <bits/stdc++.h> using namespace std; typedef long long LL; t...

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

题目链接：点我~~ 题意：敏感词屏蔽，给一堆敏感词，给一段文本，要求把文本中所有的敏感词用*代替。 思路：对敏感词建出AC自动机，在AC自动机上跑文本，可以得到每个前缀的最长匹配后缀，再将每一匹配到的段标记，最后再扫一遍输出。 #include <bits/stdc++.h> using namespace std; typedef long...

求可重叠的出现K次的最长重复子串~ 二分枚举height数组即可。 //#pragma commmpnt(linkmpr, "/STACK:102400000,102400000") #include <cstdio> #include <cstring> #include <iostream> #include ...