글 읽기 - 아호코라식 알고리즘으로 작성하였습니다.

algospot 7년 전 0

어느부분이 잘못되었는지 알고싶습니다..

#include <stdio.h>
#include <queue>
using namespace std;

#define MAX 1000000
#define TRIE 500000
#define LEN 100

int trie[TRIE+5][4], term[TRIE+5], sz;
int fail[TRIE+5];
char str[MAX+5];
char mark[LEN+5];
char cpy[LEN+5];
int h[100];

int n, m;
int cnt;

void make_hash()
{
	h['A'] = 0;
	h['G'] = 1;
	h['T'] = 2;
	h['C'] = 3;
}

void strcpy(char *a, char *b) {
	int i;
	for (i = 0; i < m; i++)
	{
		a[i] = b[i];
	}
}

void swap(char *s, int a, int b) {
	int i;
	for (i = b; i >= a; i--)
	{
		s[a + b - i] = mark[i];
	}
}

void input()
{
	scanf("%d %d", &n, &m);
	scanf("%s %s",str, mark);
}

void init()
{
	int i, j;

	//init trie
	for (i = 0; i < TRIE; i++)
	{
		fail[i] = term[i] = 0;
		
		for (j = 0; j < 4; j++)
		{
			trie[i][j] = 0;
		}
	}

	//init answer
	sz = 0;
	cnt = 0;
}

void mk_trie()
{
	int i,j,k,p,qf;
	
	//초기 문자열에 대한 trie 구성
	p = 0;

	for (k = 0; mark[k]; k++)
	{
		if (!trie[p][h[mark[k]]])
		{
			trie[p][h[mark[k]]] = ++sz;
		}
		p = trie[p][h[mark[k]]];
	}

	term[p] = 1;

	for (i = 0; i < m; i++)
	{
		for (j = i + 1; j < m;j++)
		{
			strcpy(cpy, mark);
			swap(cpy, i, j);

			p = 0;

			for (k = 0; cpy[k]; k++)
			{
				if (!trie[p][h[cpy[k]]])
				{
					trie[p][h[cpy[k]]] = ++sz;
				}
				p = trie[p][h[cpy[k]]];
			}

			term[p] = 1;
		}
	}
	
	//construct failure

	queue<int> q;
	q.push(0);
	while (!q.empty())
	{
		qf = q.front();
		q.pop();
		for (i = 0; i < 4; i++)
		{
			if (trie[qf][i] == 0) continue;
			
			p = qf;
			
			if (qf == 0) fail[trie[qf][i]] = 0;
			else
			{
				p = fail[p];
				while (p != 0 && trie[p][i] == 0)
				{
					p = fail[p];
				}
				p = trie[p][i];
				fail[trie[qf][i]] = p;
				if (term[p]) term[trie[qf][i]] = 1;
			}
			q.push(trie[qf][i]);
		}
	}
}

void process()
{
	int i, p = 0;
	for (i = 0; str[i]; i++)
	{
		while (p && !trie[p][h[str[i]]])
		{
			p = fail[p];
		}
		p = trie[p][h[str[i]]];
		if (term[p])
		{
			cnt++;
		}
	}
}

int main(){
	int T;
	make_hash();
	scanf("%d",&T);
	while (T--)
	{
		init();
		input();
		mk_trie();
		process();
		printf("%d\n", cnt);
	}
	return 0;
}

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

문제

문제

출처

ICPC

아호코라식 알고리즘으로 작성하였습니다.

algospot 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말