RE自动机
查看原帖
RE自动机
297831
idgg007楼主2021/10/16 13:25
#include<cstdio>
#include<queue>
#include<iostream>
#include<string>
#include<map>
#include<vector>
struct TireTree {
	int son[26];
	std::vector<char>is;
	int size=0;
};
TireTree New;
std::string T;
std::vector<int> fair;
std::vector<TireTree> tireTree;
void BuildTree(int node, std::string add, int k) {
	if (!add[k]) {
		tireTree[node].size++;
	} else if (!tireTree[node].son[add[k]]) {
		int l = tireTree.size();
		tireTree[node].son[add[k]-'a'] = l;
		tireTree[node].is.push_back(add[k]-'a');
		tireTree.push_back(New);
		BuildTree(l, add, k + 1);
	} else {
		BuildTree(tireTree[node].son[add[k]], add, k + 1);
	}
}
std::queue<int>queue;
void Fair() {
	fair.assign(tireTree.size(), 1);
	fair[1] = 0;
	queue.push(1);
	while (!queue.empty()) {
		int head = queue.front();
		int lenth = tireTree[head].is.size();
		for (int i = 0; i < lenth; i++) {
			queue.push(tireTree[head].son[tireTree[head].is[i]]);
			int j = fair[head];
			while (j != 0 && tireTree[j].son[tireTree[head].is[i]] == 0) {
				j = fair[j];
			}
			if (j == 0) {
				fair[tireTree[head].son[tireTree[head].is[i]]] = 1;
			} else {
				fair[tireTree[head].son[tireTree[head].is[i]]] =
				    tireTree[j].son[tireTree[head].is[i]];
			}
		}
		queue.pop();
	}
	fair[1] = 1;
}
int AcCode() {
	int SUM = 0;
	int lenth = T.size();
	int TN = 0;
	int TI = 1;
	while (TN < lenth) {
		if (tireTree[TI].size) {
			SUM+=tireTree[TI].size;
			tireTree[TI].size = 0;
		}
		if (tireTree[TI].son[T[TN]]) {
			TI = tireTree[TI].son[T[TN]];
			TN++;
		} else {
			while (TI != 1 && tireTree[TI].son[T[TN]] == 0) {
				TI = fair[TI];
				if (tireTree[TI].size) {
					SUM++;
					tireTree[TI].size = 0;
				}
			}
			while (TN < lenth && tireTree[TI].son[T[TN]] == 0) {
				TN++;
			}
		}
	}
	if (tireTree[TI].size) {
		SUM+=tireTree[TI].size;
		tireTree[TI].size = 0;
	}
	if (tireTree[TI].son[T[TN]]) {
		TI = tireTree[TI].son[T[TN]];
		TN++;
	} else {
		while (TI != 1 && tireTree[TI].son[T[TN]] == 0) {
			TI = fair[TI];
			if (tireTree[TI].size) {
				SUM++;
				tireTree[TI].size = 0;
			}
		}
		while (TN < lenth && tireTree[TI].son[T[TN]] == 0) {
			TN++;
		}
	}
	return SUM;
}
int N;
int main() {
	scanf("%d\n", &N);
	tireTree.push_back(New);
	tireTree.push_back(New);
	for (int i = 0; i < N; i++) {
		std::string getin;
		std::getline(std::cin, getin);
		BuildTree(1, getin, 0);
	}
	std::getline(std::cin, T);
	Fair();
	printf("%d", AcCode());
	return 0;
}

运行到18行的时候就崩了,这是什么情况?

2021/10/16 13:25
加载中...