[BOJ 2809] 아스키 거리

 

[문제]

 

www.acmicpc.net/problem/2809

2809번: 아스키 거리

 

[난이도]

 

- Platinum 2 (20.12.11 solved.ac 기준)

 

 

[필요 개념]

 

- 아호코라식 (Aho-corasick)

 

 

[풀이]

 

아호코라식 문자열 판별 알고리즘의 응용문제이다.

타일과 일치하는 부분을 제외한 문자의 개수를 구하는 문제인데, 단순하게 아스키 거리의 각 위치(index) 별로 

끝에 일치하는 타일들을 모두 고려한다면 시간 초과가 발생할 것 같다....? (정확하게는 모르겠다)

 

따라서, 만약 특정 index에서 끝나면서 일치하는 타일이 여러 개가 있다면, 그중에서 가장 길이가 긴 타일만 생각해줘도 충분하다. 

 

그러므로 각 타일 별로 길이를 미리 구해두고, 트라이의 각 타일 끝에 해당하는 노드에 타일의 번호를 기록해둔다.

그다음, 실패 함수를 연결시켜줄 때 해당 노드에서 일치하는 타일 중 '가장 길이가 긴 타일의 번호'를 저장해둔다.

마지막으로 아스키 거리에 해당하는 문자열을 탐색하면서, 타일의 끝인 노드에 도착하면 벡터에 해당 타일의 구간을 저장해 두고, 답을 구한다.

 

그리고, map이나 Trie *ch[26] 과 같은 방식으로 다음 노드들을 구현한다면 메모리 초과가 발생할 확률이 매우 높다.

그래서, vector를 이용하여 이용되는 문자만 메모리를 사용하도록 하였다. 

 

 

[소스 코드]

 

#include<bits/stdc++.h>
#define all(v) v.begin(), v.end()
#define sz(x) (int)x.size()
using namespace std;
using pii = pair<int, int>;

int len[5000];
int cnt[300001];
vector<pii> v;
struct Trie {
	vector<pair<char, Trie*>> ch;
	int end;
	Trie* fail;
	Trie() {
		end = -1;
		ch.clear();
		fail = nullptr;
	}
	void insert(const char* s, int num) {
		if (!*s) {
			end = num;
			return;
		}
		int now = *s - 'a';
		for (auto& i : ch) {
			if (i.first == now) return i.second->insert(s + 1, num);
		}
		ch.push_back({ now, new Trie });
		ch.back().second->insert(s + 1, num);
	}
	void init() {
		queue<Trie*> q;
		q.push(this);
		while (!q.empty()) {
			Trie* now = q.front(); q.pop();
			for (auto& i : now->ch) {
				Trie* next = i.second;
				if (now == this) next->fail = this;
				else {
					Trie* t = now->fail;
					while (t != this) {
						bool chk = true;
						for (auto j : t->ch) {
							if (j.first == i.first) {
								chk = false;
								break;
							}
						}
						if (!chk) break;
						t = t->fail;
					}
					for (auto j : t->ch) {
						if (j.first == i.first) {
							t = j.second;
							break;
						}
					}
					next->fail = t;
				}
				if (next->fail->end>=0) {
					if (next->end == -1 || (len[next->fail->end] > len[next->end])) {
						next->end = next->fail->end;
					}
				}
				q.push(next);
			}
		}
	}
	void query(const string& s) {
		Trie* cur = this;
		for (int i = 0; i < sz(s); i++) {
			int now = s[i] - 'a';
			while (cur != this) {
				bool chk = true;
				for (auto j : cur->ch) {
					if (j.first == now) {
						chk = false; 
						break;
					}
				}
				if (!chk) break;
				cur = cur->fail;
			}
			for (auto j : cur->ch) {
				if (j.first == now) {
					cur = j.second;
					break;
				}
			}
			if (cur->end >= 0) {
				v.push_back({ i - len[cur->end] + 1, i });
			}
		}
	}
};
int main(void) {
	ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
	Trie* root = new Trie;
	int N; cin >> N;
	string s; cin >> s;
	int M; cin >> M;
	vector<string> tile(M);
	for (int i = 0; i < M; i++) {
		cin >> tile[i];
		len[i] = sz(tile[i]);
		root->insert(tile[i].c_str(), i);
	}
	root->init();
	root->query(s);
	sort(all(v));
	int last = -1;
	int ans = 0;
	for (int i = 0; i < sz(v); i++) {
		if (last < v[i].first) {
			ans += v[i].first - last-1;
		}
		last = max(last, v[i].second);
	}
	ans += sz(s) - 1 - last;
	cout << ans;

}

 

PC로 보시는 것을 권장합니다. 

피드백은 언제나 환영입니다. 댓글로 달아주세요 ^-^