写点逆天的数据结构课设
C++ 代码
#include<bits/stdc++.h>
using namespace std;
#ifndef _MAP_H_
#define _MAP_H_
template<typename _Tp> // 模板类,_Tp代表队列中元素的类型
class Queue {
enum { DEFAULT_SIZE = 10 }; // 默认创建的数组大小
typedef _Tp DataType; // typedef 匹配任意类型
private:
DataType * _data = NULL; // 动态数组指针
int _begin = 0; // begin
int _end = 0; // end
size_t _capacity = (size_t)DEFAULT_SIZE; // 数组大小
void extend() {
size_t siz = size();
// 队满时才扩容
if (siz == _capacity - 1) {
// 开辟新空间
DataType * tmp = new DataType[_capacity << 1];
// 复制元素
for (int i = _begin, j = 0; i != _end; i = (i + 1) % _capacity, ++j) {
tmp[j] = _data[i];
}
// 更新begin,end,data指针,容量capacity
_begin = 0;
_end = siz;
delete [] _data; // 释放原有空间
_data = tmp;
_capacity <<= 1;
}
}
public:
Queue() {
// 创建动态数组
_data = new DataType[_capacity];
}
~Queue() {
// 释放动态创建的数组
if (_data) delete [] _data;
}
void push(const DataType & e) {
extend(); // 扩容
_data[_end] = e;
_end = (_end + 1) % _capacity;
}
void pop() {
if (!empty()) { // 不空才出队
_data[_begin].~DataType(); // 释放begin处的元素
_begin = (_begin + 1) % _capacity; // 循环后移
}
}
const DataType & front() const {
return _data[_begin]; // 取begin处的元素,即队头
}
size_t size() const {
return (_end - _begin + _capacity) % _capacity; // 队列大小
}
bool empty() const {
return _begin == _end; // 判空
}
};
#endif
namespace Aho_Corasick_automaton {
typedef int Status;
const int CharMax = 26;
const int OK = 1;
const int ERROR = -1;
struct TrieNode {
int flag; //标记此处是否为字符串结尾
int cnt; //此节点被匹配到的次数
TrieNode* Fail; //失配指针
TrieNode* Next[CharMax]; //子节点指针
TrieNode(int id) {
flag = id;
cnt = 0;
memset(Next,0,sizeof Next);
Fail = NULL;
}
};
typedef TrieNode* TrieTree;
Status Trie_Tree_insert(string s, TrieTree root, int id) { //在Trie树中插入一个新字符串。
if(s.empty()) return ERROR; //字符串为空,插入失败,返回ERROR
TrieTree p = root;
for(char c : s) {
int t = c - 'a';
if(p->Next[t] == NULL) p->Next[t] = new TrieNode(0);
p = p->Next[t];
}
p->flag = id; //对字符串末尾进行标记
return OK;
}
Status Fail_Tree_build(TrieTree root, stack<TrieTree> &BFS_Sequence) {
Queue<TrieTree> q;
//向队列中推入底层点
root->Fail = root;
for(int i=0;i<CharMax;i++) {
TrieTree p = root->Next[i];
if(p != NULL) {
q.push(p);
p->Fail = root;
}
else {
root->Next[i] = root;
}
}
//广度优先遍历,建立Trie图,并储存BFS序列
while(!q.empty()) {
TrieTree t = q.front();
BFS_Sequence.push(t);
q.pop();
for(int i=0;i<26;i++) {
TrieTree p = t->Next[i];
if(!p) t->Next[i] = t->Fail->Next[i];
else {
p->Fail = t->Fail->Next[i];
if(p->Fail == NULL) p->Fail = root;
q.push(p);
}
}
}
return OK;
}
Status AC_automaton(string s, TrieTree root, int ElementSum, map<int,int> mmp) {
stack<TrieTree> BFS_Sequence;
//拓扑序
long long ans[ElementSum+1];
Fail_Tree_build(root, BFS_Sequence);
TrieTree p = root;
for(char c : s) {
if(c == ' ') {
p = root;
continue;
}
int t = c - 'a';
p = p->Next[t];
if(p == NULL) p = root;
p -> cnt += 1;
}
while(!BFS_Sequence.empty()) {
TrieTree p = BFS_Sequence.top();
BFS_Sequence.pop();
p->Fail->cnt += p->cnt;
if(p->flag) {
ans[p->flag] = p->cnt;
}
}
for(int i=1;i<=ElementSum;i++) {
cout << ans[mmp[i]] << '\n';
}
return OK;
}
}
using namespace Aho_Corasick_automaton;
int main() {
std::ios::sync_with_stdio(0);
std::cin.tie(0);
std::cout.tie(0);
TrieTree root = new TrieNode(0);
int t = 1;
cin >> t;
if(t == 1) {
cout << 1 << '\n';
return 0;
}
string s, ss;
map<string,int> mp;
map<int,int> mmp;
for(int i=1;i<=t;i++) {
cin >> s;
ss += " " + s;
if(!mp[s]) Trie_Tree_insert(s, root, i), mp[s] = i;
mmp[i] = mp[s];
}
AC_automaton(ss,root,t,mmp);
}
牛的
链式写法的AC自动机是真逆天
真的强