Hiho#1366 : 逆序单词（Trie树）

博主链接

题目链接

题意：

给你N个串，求出有多少对逆序串，即一个串逆序是另外一个串

题解：

每输入一个串将其插入trie树就判断下trie树中是否有他的逆序串，如果有就ans++

代码：

#include<stdio.h>
#include<bits/stdc++.h>
#define ll long long int
#define max_n 1000050
#define max_tot 500050
#define met(a) memset(a,0,sizeof(a))
#define fup(i,a,n,b) for(int i=a;i<n;i+=b)
#define fow(j,a,n,b) for(int j=a;j>0;j-=b)
#define MOD(x) (x)%mod
using namespace std;
const int maxn = 1e5 + 7;
struct Ac {
	struct state{  //节点状态
		int next[26];
		int fail, cnt;//指针fail 到这个节点有cnt个串结束
	}stable[max_tot];
	int size;  //当前AC自动机节点个数
	queue<int>q;
	void init() {  //初始化
		for (int i = 0; i < max_tot; i++) {
			met(stable[i].next);
			stable[i].fail = stable[i].cnt = 0;
		}
		size = 1;
		while (!q.empty())q.pop();
	}
	int ans = 0;
	void insert(char *s) {  //将模式串插入trie树
		int now = 0; //代表走到那个节点
		for (int i = 0;s[i]; i++) {
			char ch = s[i];  
			if (!stable[now].next[ch - 'a'])  //节点不存在该字母边，则新建一个
				stable[now].next[ch - 'a'] = size++;
			now = stable[now].next[ch - 'a'];
		}
		stable[now].cnt++;//结束位置++；
	}
	void build() {  //构造失配fail指针，要构造当前节点fail指针需先构造爸爸节点
		stable[0].fail = -1;
		q.push(0);
		while (!q.empty()) {
			int u = q.front();
			q.pop();
			for (int i = 0; i < 26; i++) {
				if (stable[u].next[i]) {  //如果有i这条边 枚举下他儿子
					if (u == 0)stable[stable[u].next[i]].fail = 0;
					else {
						int v = stable[u].fail;
						while (v != -1) {  //一直找它祖先的fail
							if (stable[v].next[i]) {  //如果他某个祖先有i这条边
								int a = stable[u].next[i];
								stable[a].fail = stable[v].next[i];
								break; 
							}
							v = stable[v].fail;
						}
						int a = stable[u].next[i];
						if (v == -1)stable[a].fail = 0;//如果没找到 ，就只能指向0
					}
					q.push(stable[u].next[i]);  //节点加进去
				}
			}
		}
	}
	int get(int u) {  //算所有祖先的和
		int res = 0;
		while (u) {
			res = res + stable[u].cnt;
			stable[u].cnt = 0;  //计算后不再计算，如果要计算不清零
			u = stable[u].fail;
		}
		return res;
	}
	int match(char *s) {   //匹配
		int res = 0, now = 0;
		for (int i = 0; s[i]; i++) {
			char ch = s[i];
			if (stable[now].next[ch - 'a'])  //如果当前状态太能找到后继节点，则走他
				now = stable[now].next[ch - 'a'];
			else {  //否则只能跳爸爸
				int p = stable[now].fail;
				while (p != -1 && stable[p].next[ch - 'a'] == 0)p = stable[p].fail;
				if (p == -1)now = 0;  //始终没找到，只能指根节点
				else now = stable[p].next[ch - 'a'];  //找到就跳对应地方
			}
			if (stable[now].cnt)res = res + get(now);
		}
		return res;
	}

	void check(char *s) {
		int now = 0;/
		int n = strlen(s);
		for (int i =n-1 ; i>=0; i--) {
			int ch = s[i];
			if (!stable[now].next[ch - 'a'])return;
			now=stable[now].next[ch - 'a'];
		}
		if (stable[now].cnt)ans++;
	}
}Ac;

char s[max_n];
int main(int argc, char *argv[]) {
	/*ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);*/
	int t,n;
	Ac.init();
	scanf("%d", &n);
	for (int i = 0; i < n; i++) {
		scanf("%s", s);
		Ac.check(s);
		Ac.insert(s);
	}
	printf("%d\n", Ac.ans);
	return 0;
}