代码放这里。看注释。
```cpp
#include <string>
#include <vector>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <map>
#define PATTERN_COUNT 150
#define PATTERN_LENGTH 71
#define TEXT_LENGTH 1000001
class TreeNode {
public:
inline TreeNode() { memset(children, 0, sizeof(children)); }
TreeNode* children[26];
char pattern = -1;
int value = -1;
};
char patternVec[PATTERN_COUNT][PATTERN_LENGTH];
char strText[TEXT_LENGTH];
TreeNode* root;
inline void insert2tree(int index, const std::string& strPattern, TreeNode* pRoot) {
TreeNode* pNode = pRoot;
for (auto v : strPattern) {
if (pNode->children[v - 'a']) {
pNode = pNode->children[v - 'a'];
continue;
}
auto pNodeTemp = new TreeNode;
pNodeTemp->pattern = v;
pNode->children[v - 'a'] = pNodeTemp;
pNode = pNodeTemp;
}
pNode->value = index;
}
inline void getInput(int& N, std::istream& obj = std::cin) {
N = 0;
obj >> N;
for (int i = 0; i < N; i++) {
std::string strTemp;
obj >> strTemp;
insert2tree(i, strTemp, root);
memcpy(patternVec[i], strTemp.c_str(), strTemp.size());
}
obj >> strText;
}
inline void compute(int paternCount, int& maxCount, std::vector<std::string>& maxTextVec) {
int countVec[PATTERN_COUNT];
memset(countVec, 0, sizeof(countVec));
for (size_t index = 0; index < TEXT_LENGTH; ++index) {
if (!strText[index]) break;
TreeNode* pNode = root;
for (size_t subIndex = index; subIndex < TEXT_LENGTH; ++subIndex) {
if (!strText[subIndex]) break;
auto found = pNode->children[strText[subIndex] - 'a'];
if (found != nullptr) pNode = found;
else break;
}
if (pNode->value != -1) ++countVec[pNode->value];
}
// Compute the max
maxCount = 0;
for (size_t index = 0; index < paternCount; ++index) if (countVec[index] > maxCount) maxCount = countVec[index];
for (size_t index = 0; index < paternCount; ++index) if (countVec[index] == maxCount) maxTextVec.push_back(patternVec[index]);
}
inline void output(int maxCount, const std::vector<std::string>& maxTextVec, std::ostream& obj = std::cout) {
obj << maxCount << std::endl;
for (auto it : maxTextVec) obj << it << std::endl;
}
std::vector<std::string> maxTextVec;
int main() {
std::cin.tie(nullptr)->sync_with_stdio(false);
std::cout.tie(nullptr);
int N = 0;
do {
root = new TreeNode;
memset(&patternVec, 0, sizeof(patternVec));
memset(&strText, 0, sizeof(strText));
//#1 get input for current group
getInput(N);
// When the N = 0 is input, stop the program
if (!N) break;
//#2 compute the max pattern string. use vector to keep equal count strings
int maxCount = 0;
compute(N, maxCount, maxTextVec);
//#3 output result for this group
output(maxCount, maxTextVec);
maxTextVec.clear();
delete root;
} while (1);
return 0;
}
```
by Ruiqun2009 @ 2023-01-07 23:33:43
好像光 500ms [卡不掉](https://www.luogu.com.cn/record/98980592)我的做法
by Ruiqun2009 @ 2023-01-07 23:35:06
![](//图.tk/1) 是我的 AC 自动机不太正常吗,空间限制远远大于 32MB,时间也花了 1s 多。
[我写的 AC 自动机。](https://www.luogu.com.cn/record/81259748)
by Shunpower @ 2023-01-07 23:51:49
@[Zealous_YH](/user/399150) 把流同步关了试试?
by Ruiqun2009 @ 2023-01-08 12:10:25
@[Ruiqun2009](/user/589895) 我昨天晚上重新写了一下发现我的写法乱七八糟,现在改了之后[确实很快](https://www.luogu.com.cn/record/99007712)。
by Shunpower @ 2023-01-08 12:31:46
@[Zealous_YH](/user/399150) 其实把 `endl` 改成 `'\n'` 更快。另外,可以加上
```cpp
cin.tie(0);
cout.tie(0);
```
会跑得更快
by Ruiqun2009 @ 2023-01-08 13:16:16
@[Ruiqun2009](/user/589895) THX
by Shunpower @ 2023-01-08 15:10:18