이진 trie(btrie)

문제로 이해해 봅시다.

아래와 같은 0 혹은 1 을 가지는 패턴 표가 주어지고,

p1=10
p2=111
p3=11010
p4=11
p5=0
p6=1000
p7=100000
p8=100001

110 이 주어질 때 주어진 문자열의 앞 부분(prefix)과 최대로 많이 일치하는 패턴은?... p4 ....

1011 이 주어질 때 이 문자열의 앞 부분과 최대로 많이 일치하는 패턴은? .... p1...

유제.

1. 10001011 이 주어질 때? p6

2. 11010101 이 주어질때? p3

어떻게 구현하나??

1.막 하기

아마 눈으로 한 방법대로 하면 O(n^3) 정도로 구현 할 수 있습니다.

2.binary trie 사용

이 패턴 표를 가지고 0 은 왼쪽으로 1 은 오른쪽으로 가면서 이진 트리를 구축 합니다. (linked list 사용) 터미널 노드는 패턴의 번호를 가집니다.

• p1=10 구축하기

  

• p2=111 구축하기

  

• p3=11010 구축하기

  

• ...

분석

• 패턴 테이블을 btrie 로 구축 O(n^2)
• 패턴 찾는 것:O(n)

시간 복잡도는 O(n^2)

소스:

struct node
{
	struct node *lchild,*rchild;
	int data;
};

struct node *root;
FILE *fp1,*fp2;
int last_state;// 답 

//binary trie 구축 
//패턴은 table.txt 파일에 저장되어 있다고 함.

void init()
{
	char buffer[35];
	int n = 1,i;
	struct node *p,*q;
	
	fp1 = fopen("table.txt","r");
	
	root = (struct node*)calloc(1,sizeof(struct node));
	while (fgets(buffer,131,fp1)! =  NULL) {
		q = root;
		for(i = 0;buffer[i]!='\n';i++){
			p = q;
			if (buffer[i] = ='1') q = q->rchild; 
			else q = q->lchild;
			if (q == NULL){
				q = (struct node*)calloc(1,sizeof(struct node));
				if (buffer[i] == '1') p->rchild = q;
				else p->lchild = q;
			}
		}
		q->data = n;
		n++;
	}
	fclose(fp1);
}

//구축된 binary trie 사용해서 막힌 곳이 나올때 까지 따라감.
void process()
{
	char buffer[2001];
	int i;
	struct node *p;
	
	fp2 = fopen("input.txt","r");
	fgets(buffer,10001,fp2);
	
	p = root;
	for(i = 0;buffer[i]!='\n';i++){
		if(buffer[i] == '1') p = p->rchild;
		else p = p->lchild;
		if (p  == NULL) break;
		if (p->data != 0) last_state = p->data;
	}
	fclose(fp2);
}

//답 출력
void output()
{
	printf("%d\n",last_state);
}

int main()
{
	init();
	process();
	output();
	return 0;
}

출처:dovelet