압축 트라이 (Compressed Trie)

#include <bits/stdc++.h>
using namespace std;

struct node {
	bool valid; // 해당 노드가 valid한지 나타내는 변수
	int child[26]; // 해당 노드의 각 자식 노드가 가리키는 인덱스
	node() {
		valid = false;
		memset(child, -1, sizeof(child)); // 노드를 생성할 때 child 배열을 -1로 초기화를 해줍니다.
	}
};
vector<node> trie;

int init() {
	node x;
	trie.push_back(x);
	return (int)trie.size() - 1;
}

void add(int n, string &s, int i) {
	if (i == s.length()) { // s의 모든 문자를 추가했으면 valid 값을 true로 바꾸고 종료시킵니다.
		trie[n].valid = true;
		return;
	}
	int c = s[i] - 'a';
	if (trie[n].child[c] == -1) { // c로 향하는 자식이 없으면 새로운 노드를 만들어 연결시킵니다.
		int next = init();
		trie[n].child[c] = next;
	}
	add(trie[n].child[c], s, i + 1);
}

string t;
int d[100000];
const int MOD = 1000000007;
int go(int N) {
	if (N == t.length()) return 1;
	int &ret = d[N];
	if (~ret) return ret;
	ret = 0;
	int n = 0; // 트라이에서의 현재 위치한 정점 번호
	while(1) {
		if (N == t.length()) break;
		int c = t[N] - 'a';
		if (trie[n].child[c] == -1) break; // t[N]에 해당하는 자식이 없으면 반복문을 탈출합니다.
		n = trie[n].child[c]; // 있으면 해당 노드로 이동합니다.
		if (trie[n].valid) ret = (ret + go(N+1)) % MOD; // 그 노드가 valid 하다면 d[N+1]을 더해줍니다.
													   // 이 때의 N이 우리가 지금 채우고 있는 d[N]의 N과 다른 값이라는 점에 주의합니다.
		N++; // 다음 문자로 넘어갑니다.
	}
	return ret;
}
int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	memset(d, -1, sizeof(d));

	init(); // 트라이의 루트를 만들어줍니다. 루트의 번호는 0입니다.
	int n;
	cin >> n;
	for(int i = 0; i < n; i++) {
		string s;
		cin >> s;
		add(0, s, 0); // s를 트라이에 추가합니다.
	}
	cin >> t;
	cout << go(0) << '\n';
	return 0;
}

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;

struct node {
	bool valid;
	int child[26], child_cnt; // 추가로 자식의 개수를 나타내는 변수를 만들어줍니다. 자식의 개수도 압축의 기준이기 때문에..
	int len, H; // 정점에 해당하는 문자열의 길이와 해시값을 의미합니다.
	node() {
		valid = false;
		child_cnt = 0;
		memset(child, -1, sizeof(child));
	}
};
vector<node> trie;

int init() {
	node x;
	trie.push_back(x);
	return (int)trie.size() - 1;
}

void add(int n, string &s, int i) {
	if (i == s.length()) {
		trie[n].valid = true;
		return;
	}
	int c = s[i] - 'a';
	if (trie[n].child[c] == -1) {
		trie[n].child_cnt++; // 새로운 자식이 생기면 child_cnt를 1 증가시킵니다.
		int next = init();
		trie[n].child[c] = next;
	}
	add(trie[n].child[c], s, i + 1);
}

string t;
ll h[100001], p[100001];
int d[100000];
const int MOD = 1000000021;

tuple<int,int,int> dfs2(int n, int d, int h) { // (정점번호, 문자열 길이, 문자열의 해시값)을 반환하는 함수
	if(trie[n].valid || trie[n].child_cnt > 1)return {n, d, h}; // 정점이 valid하거나 자식이 2개 이상 있으면 여기까지만 압축을 진행하고, 현재까지의 정보들(정점 번호, 문자열 길이, 해시값)을 반환합니다.
	for(int i = 0; i < 26; i++) {
		if(trie[n].child[i] != -1)
			return dfs2(trie[n].child[i], d + 1, (1LL * h * 37 + i + 1) % MOD); // h[i] = (h[i-1]*p) % MOD 를 여기에도 적용시켜 인자로 넘깁니다. 이 때 자식의 개수가 1개임이 보장되어있으므로 바로 return을 해줘도 됩니다.
	}
	return {};
}
void dfs(int n) {
	for(int i = 0; i < 26; i++) {
		if(trie[n].child[i] != -1) {
			auto [nx, L, H] = dfs2(trie[n].child[i], 1, i + 1); // nx, L, H는 각각 도착 정점, 문자열 길이, 해시값을 의미합니다.
			trie[n].child[i] = nx, trie[nx].len = L, trie[nx].H = H; // 현재 정점 n의 i에 해당하는 자식에 nx를 연결시키고, nx에 해당하는 문자열 정보도 수정합니다.
			dfs(nx); // 후에 다시 nx부터 압축을 진행합니다.
		}
	}
}

ll Hash(int l,int r) { // t[l .. r]에 해당하는 해시값을 구하는 함수
	l++, r++;
	int t = r - l + 1;
	ll res = (h[r] - h[l - 1] * p[t]) % MOD;
	if (res < 0) res += MOD;
	return res;
}

int go(int N){
	if(N==t.length()) return 1;
	int &ret = d[N];
	if(~ret) return ret;
	ret = 0;
	int n = 0;
	while(1) {
		if(N == t.length()) break;
		int nx = trie[n].child[t[N] - 'a']; // t[N]에 해당하는 자식의 정점 번호
		if(nx==-1) break; // t[N]에 해당하는 자식이 없다면 break 해줍니다.
		int L = trie[nx].len;
		if(N + L > t.length()) break; // N+L이 t의 길이보다 큰지, 즉 이번에 확인할 문자열의 범위가 t의 범위를 벗어나는지 확인합니다.
		if(trie[nx].H == Hash(N, N + L - 1)) { // nx에 저장되어있는 해시값과 T[N .. N+L-1]의 해시값이 같으면 두 문자열이 일치하여 해당 정점으로 갈 수 있음을 의미합니다.
			if(trie[nx].valid) ret = (ret + go(N + L)) % 1000000007; // 해당 노드가 valid하면 d[N+L]을 더해줍니다. T[N ..]을 T[N .. N+L-1]과 T[N+L ..]로 나눈다고 생각하면 됩니다.
			n = nx;
			N += L;
		} else break; // 해시값이 다르면 둘은 다른 문자열이므로 반복문을 탈출해줍니다.
	}
	return ret;
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	memset(d, -1, sizeof(d));
	p[0] = 1;
	for(int i = 1; i <= 100000; i++) p[i] = p[i - 1] * 37 % MOD; // p[i]=37^i

	init();
	int n;
	cin >> n;
	for(int i = 0; i < n; i++) {
		string s;
		cin >> s;
		add(0, s, 0);
	}
	dfs(0); // 트라이 압축
	cin >> t;
	for(int i = 0; i < (int)t.length(); i++) h[i + 1] = (h[i] * 37 + t[i] - 'a' + 1) % MOD; // t의 해시값을 저장합니다.
	cout << go(0) << '\n';
}