字符串匹配
Knuth-Morris-Pratt algorithm
对于每次失配之后，我都不会从头重新开始枚举，而是根据我已经得知的数据，从某个特定的位置开始匹配；而对于模式串的每一位，都有唯一的“特定变化位置”，这个在失配之后的特定变化位置可以帮助我们利用已有的数据不用从头匹配，从而节约时间。
时间复杂度\(\Theta(n + m)\)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
| #include <cstdio>
#include <cstring>
#include <vector>
int length1, length2, next_index[1010];
char str1[1000010], str2[1010];
std::vector<int> appear_index;
inline void KnuthMorrisPratt() {
for (register int i(1), j(-1); i < length2; ++i) {
while (str2[i] != str2[j + 1] && ~j) j = next_index[j];
if (str2[i] == str2[j + 1]) next_index[i] = ++j;
}
for (register int i(0), j(-1); i < length1; ++i) {
while (str1[i] != str2[j + 1] && ~j) j = next_index[j];
if (str1[i] == str2[j + 1] && ++j == length2) {
appear_index.push_back(i - length2 + 1),
j = next_index[length2];
}
}
}
int main(int argc, char const *argv[]) {
scanf("%s %s", str1, str2);
length1 = strlen(str1), length2 = strlen(str2);
KnuthMorrisPratt();
for (auto i : appear_index) {
printf("%d\n", i);
}
for (register int i(0); i < length2; ++i) {
printf(i == length2 - 1 ? "%d\n" : "%d ", next_index[i]);
}
return 0;
}
|
Aho-Corasick algorithm
现在我也只能咕咕咕咕咕咕咕
最长回文子串
Manacher's algorithm
在字符串的两端和每两个字符间插入一个#,
找到每一个字符作为回文中心时的最长回文串的半径。对于每一个字符,
找到以它为回文中心的子串,
该子串中每一个字符在该子串内不经过回文中心的范围是对称的,
剩下的暴力统计即可。
下面我给出的代码速度比较慢,
但用string类可以更方便地得到该子串。
时间复杂度: \(\Theta(n)\)
题目链接: Luogu
P3805 【模板】manacher算法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
| #include <vector>
#include <string>
#include <cstdio>
#include <iostream>
#include <algorithm>
inline std::string Manacher(const std::string &str){
register std::string tmp("$#");
for (auto i : str) {
(tmp += i) += '#';
}
register int s_size(tmp.length()), max_sub_length(-1), max_sub_index(-1), index(0), _max(0);
register std::vector<int> p(s_size, 0);
for (register int i(1); i < s_size; ++i){
p[i] = i < _max ? std::min(p[(index << 1) - i], _max - i) : 1;
while (tmp[i - p[i]] == tmp[i + p[i]]) ++p[i];
if (_max < i + p[i]) {
index = i,
_max = i + p[i];
}
if (p[i] - 1 > max_sub_length) {
max_sub_length = p[i] - 1, max_sub_index = i;
}
}
auto ret = str.cbegin() + ((max_sub_index - max_sub_length - 1) >> 1);
return std::string(ret, ret + max_sub_length);
}
std::string str;
int main(int argc, char const *argv[]) {
std::cin >> str;
printf("%lu\n", Manacher(str).length());
return 0;
}
|