acmicpc.net 5052(트라이), 9250(아호 코라식)

https://www.acmicpc.net/problem/5052

트라이를 이용하면 된다. 

전화번호 목록을 받아서 긴 길이->짧은 길이 순으로 정렬한다.

그 후에 insert를 하기전에 이 전화번호가 다른곳에 포함되있는지 확인한다.

#include<queue>
#include<cstdio>
#include<cstring>
#include<cassert>
#include<iostream>
#include<string>
#include<vector>
#include <algorithm>
using namespace std;

const int ALPHABETS = 10;
int toNumber(char ch) { return ch - '0'; }

struct LinkedListNode {
	int elem;
	LinkedListNode* next;

	LinkedListNode(int _elem, LinkedListNode* _next) : elem(_elem), next(_next) {
	}
};

// 트라이의 한 노드를 나타내는 객체
struct TrieNode {
	TrieNode* children[ALPHABETS];
	// 이 노드가 종료 노드인가?
	bool terminal;

	TrieNode() : terminal(false) {
		memset(children, 0, sizeof(children));
	}

	~TrieNode() {
		for(int i = 0; i < ALPHABETS; i++)
			if(children[i])
				delete children[i];
	}

	// 이 노드를 루트로 하는 트라이에 문자열 key 를 추가한다.
	void insert(const char* key) {
		// 문자열이 끝나면 terminal 만 참으로 바꾸고 종료
		if(*key == 0)
			terminal = true;
		else {
			int next = toNumber(*key);
			// 해당 자식 노드가 없다면 생성한다
			if(children[next] == NULL)
				children[next] = new TrieNode();
			// 해당 자식 노드로 재귀호출
			children[next]->insert(key + 1);
		}
	}

	// 이 노드를 루트로 하는 트라이에 문자열 key 와 대응되는 노드를 찾는다.
	// 없으면 NULL 을 반환한다.
	TrieNode* find(const char* key) {
		if(*key == 0) return this;
		int next = toNumber(*key);
		if(children[next] == NULL) 
			return NULL;
		return children[next]->find(key+1);
	}
};

char phone[10000][11];
bool _reverse(pair<int ,char* > a, pair<int, char* > b) { return a.first > b.first; }
int main() 
{
	int t;
	cin>>t;
	for(int i=0;i<t;i++)
	{
		TrieNode *trie = new TrieNode();
		int n;
		vector<pair<int, char*>> save;
		cin>>n;
		for(int j=0;j<n;j++)
		{
			cin>>phone[j];
			save.push_back(make_pair(strlen(phone[j]), phone[j]));
		}
		sort(save.begin(),save.end(),_reverse);
		//for(int j=0;j<n;j++)
		//	cout<<j<<" = "<<save[j].first<<" "<<save[j].second<<endl;
		bool flag = true;
		for(int j=0;j<n;j++)
		{
			if(j>0 && trie->find(save[j].second))
				flag=false;
			trie->insert(save[j].second);
		}
		if(flag) cout<<"YES\n";
		else cout<<"NO\n";
	}
	return 0;
}

https://www.acmicpc.net/problem/9250

카테고리에 적어놓은 아호코라식 기본 소스코드에서 ahoCorasick함수, test함수만 변경하고

입력받아서 실행하면 된다.

#include<map>
#include<queue>
#include<cstdio>
#include<cstring>
#include<cassert>
#include<iostream>
#include<string>
#include<vector>
using namespace std;

// 알파벳 소문자를 저장하는 경우 각 노드는 26개의 자손을 가질 수 있다
const int ALPHABETS = 26;
int toNumber(char ch) { return ch - 'a'; }

struct LinkedListNode {

	int elem;
	LinkedListNode* next;

	LinkedListNode(int _elem, LinkedListNode* _next) : elem(_elem), next(_next) {
	}

};

struct TrieDict {
	TrieDict* children[ALPHABETS];
	int terminal;

	// 이 노드에서 매칭이 실패했을 때 이 곳으로 가서 계속한다.
	// 이 노드에 대응되는 문자열의 접미사이면서 트라이에 포함된 최대 문자열.
	TrieDict* fail;
	// 이 노드가 방문되었을 때 등장하는 문자열들의 번호
	LinkedListNode* output;

	TrieDict() : terminal(-1), output(NULL) {
		memset(children, 0, sizeof(children));
	}

	~TrieDict() {
		for(int i = 0; i < ALPHABETS; i++)
			if(children[i])
				delete children[i];
	}

	// 이 노드를 루트로 하는 트라이에 번호가 id 인 문자열 key 를 추가한다
	void insert(const char* key, int id) {
		// 문자열이 끝나면 terminal 만 참으로 바꾸고 종료
		if(*key == 0)
			terminal = id;
		else {
			int next = toNumber(*key);
			// 해당 자식 노드가 없다면 생성한다
			if(children[next] == NULL)
				children[next] = new TrieDict();
			// 해당 자식 노드로 재귀호출
			children[next]->insert(key + 1, id);
		}
	}

	TrieDict* find(const char* key) {
		if(*key == 0) return this;
		int next = toNumber(*key);
		if(children[next] == NULL) return NULL;
		return children[next]->find(key+1);
	}
};

void calcFailureFunction(TrieDict* root) {
	queue<TrieDict*> q;
	// 루트의 fail 함수는 자기 자신
	root->fail = root;
	q.push(root);
	while(!q.empty()) {
		TrieDict* here = q.front();
		q.pop();
		for(int edge = 0; edge < ALPHABETS; ++edge) {
			if(!here->children[edge]) continue;

			TrieDict* child = here->children[edge];

			// 1레벨 노드의 실패 연결은 항상 루트
			if(here == root)
				child->fail = root;
			else {
				TrieDict* t = here->fail;
				while(t != root && t->children[edge] == NULL)
					t = t->fail;
				if(t->children[edge]) t = t->children[edge];
				child->fail = t;
			}
			if(child->terminal != -1)
				child->output = new LinkedListNode(child->terminal,
						child->fail->output);
			else
				child->output = child->fail->output;

			q.push(child);
		}
	}
}

template<class CALLBACK>
bool ahoCorasick(const string& s, TrieDict* trie, CALLBACK callback) {
	TrieDict* state = trie;
	for(int i = 0; i < s.size(); i++) {
		int chr = toNumber(s[i]);
		while(state != trie && state->children[chr] == NULL)
			state = state->fail;
		if(state->children[chr]) state = state->children[chr];
		for(LinkedListNode* t = state->output; t; t = t->next)
			return callback(i, t->elem);
	}
	return false;
}


TrieDict* find(TrieDict* node, const char* key) {
	if(*key == 0) return node;
	int next = toNumber(*key);
	if(node->children[next] == NULL) return NULL;
	return find(node->children[next], key+1);
}

bool test(int a, int b) {
	return true;
}

int main() 
{
	int n,q;
	cin>>n;
	TrieDict* trie = new TrieDict();
	for(int i=0;i<n;i++)
	{
		char str[101];
		cin>>str;
		trie->insert(str, i);
	}
	calcFailureFunction(trie);
	cin>>q;
	for(int i=0;i<q;i++)
	{
		char str[10001];
		cin>>str;
		if(ahoCorasick(string(str),trie,test)==1)
			cout<<"YES\n";
		else
			cout<<"NO\n";
	}

	return 0;
}