글 읽기 - 아호코라식 사용하는데 런타임에러 + 시간초과 등등 여러가지 문제가 있습니다..

alsidnf 4년 전 0

현재 여러가지 문제가 있는것 같은데... 일단 올린 코드 그대로 제출하면 런타임 에러가 뜹니다..

그리고 스캔받는 방식을 gets로 바꾸어 보았는데 시간초과가 뜹니다.. 도와주세요...

#include <cstdio>
#include <algorithm>
#include <queue>
#define GO_MAX 86
using namespace std;
int N, M, ctoi[128];
struct Trie {
	Trie *go[GO_MAX];
	Trie *fail;
	bool output;
	Trie() {
		fill(go, go + GO_MAX, nullptr);
		output = false;
	}
	~Trie() {
		for (int i = 0; i < GO_MAX; i++) {
			if (go[i]) delete go[i];
		}
	}
	void insert(const char *key) {
		if (*key == '\0' || output) {
			output = true;
			return;
		}
		int next = ctoi[*key];
		if (!go[next]) go[next] = new Trie;
		go[next]->insert(key + 1);
	}
}*root;
//char -> int 로하는 ctoi배열 만들기
void makectoi() {
	for (char c = 'a'; c <= 'z'; c++) ctoi[c] = c - 'a';
	for (char c = 'A'; c <= 'Z'; c++) ctoi[c] = c - 'A' + 26;
	for (char c = '0'; c <= '9'; c++) ctoi[c] = c - '0' + 52;
	ctoi['!'] = 62;
	ctoi['?'] = 63;
	ctoi['.'] = 64;
	ctoi[','] = 65;
	ctoi[':'] = 66;
	ctoi[';'] = 67;
	ctoi['-'] = 68;
	ctoi['_'] = 69;
	ctoi['\''] = 70;
	ctoi['#'] = 71;
	ctoi['$'] = 72;
	ctoi['%'] = 73;
	ctoi['/'] = 74;
	ctoi['='] = 75;
	ctoi['*'] = 76;
	ctoi['+'] = 77;
	ctoi['('] = 78;
	ctoi[')'] = 79;
	ctoi['{'] = 80;
	ctoi['}'] = 81;
	ctoi['['] = 82;
	ctoi[']'] = 83;
	ctoi['&'] = 84;
	ctoi[' '] = 85;
}
int main()
{
	makectoi();
	while (1)
	{
		scanf("%d %d", &N, &M);
		if (!N && !M) return 0;
		root = new Trie;
		char imot[20];
        //트라이 생성
		for (int i = 0; i < N; i++) {
			scanf("%s", imot);
			root->insert(imot);
		}
        //fail함수 만들기
		queue<Trie*> Q;
		Q.push(root);
		root->fail = root;
		while (!Q.empty())
		{
			Trie *curr = Q.front(); Q.pop();
			for (int i = 0; i < GO_MAX; i++) {
				Trie *next = curr->go[i];
				if (!next) continue;
				if (curr == root) next->fail = curr;
				else {
					Trie *dist = curr->fail;
					while (dist != root && !dist->go[i]) dist = dist->fail;
					if (dist->go[i]) dist = dist->go[i];
					next->fail = dist;
				}
				Q.push(next);
			}
		}
        // 문자열 내 문자 찾기
		char str[90],cc;
		int ans = 0;
		scanf(" ");
		while (M--) {
			for (int i = 0;; i++) {
				scanf("%c", &str[i]);
				if (str[i] == '\n') {
					str[i] = 0;
					break;
				}
			}
			Trie *curr = root;
			for (int c = 0; str[c]; c++) {
				int next = ctoi[str[c]];
				while (curr != root && !curr->go[next]) curr = curr->fail;
				if (curr->go[next]) {
					curr = curr->go[next];
				}
				if (curr->output) {
					ans++;
					curr = root;
				}
			}
		}
		printf("%d\n", ans);
		delete root;
	}
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

아호코라식 사용하는데 런타임에러 + 시간초과 등등 여러가지 문제가 있습니다..

alsidnf 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말