삼성 sw 3135. 홍준이의 사전놀이

부분 문자열을 찾는 방법은 하나의 긴 문자열에서 부분 문자열을 찾는다면 KMP가 유용하겠지만

문자열 집합에서 특정 문자열을 갖는 문자열 개수를 찾는 문제는 트라이도 쉽게 사용가능하다.

트라이는 알파벳 26개에 대한 자식 노드를 만들고, 카운트를 담은 구조체를 선언한다

루트 노드를 초기화 하고, 전체 부분 집합을 root에서부터 insert한다.

만약 abcd, abde , abbbb라는 문자열 집합이 있다고 하면 root에서 부터 자식 알파벳 노드 중 a가 없으므로

a에 대한 노드를 만들고 a에서 다시 시작해서 b를 만들고 c, d 차례로 만들어 내려간다 그리고 노드하나를 만들때마다 

해당 노드까지 갖는 문자열은 1개가 추가되는 것이므로 cnt를 1만큼 늘려준다.

두번째 abde를 삽입한다면 a는 만들어 졌으므로 새로 노드를 만들진 않고 cnt만 늘려준다 . 즉 a를 부분 문자열로 갖는 문자열은 벌써 2개가 된것이다. 

그리고 a의 자식 노드중 b도 있으므로 마찬가지로 카운트만 , b의 자식노드중 아직 d는 없으므로 새롭게 만들고 카운트 상승

 

이와같은 과정을 반복하는 식으로 insert를 해결하고 패턴을 찾는 것은. 

root로 부터 하나씩 타고 내려가는 식으로 가다가 패턴이 끝나기도 전에 일치하는 자식이 없다면 return 0로 없다는 것을 나타내고 패턴이 끝날때 까지 자식노드가 있어서 타고 내려온 경우 마지막 자식노드의 cnt를 return하면 해당 패턴을 부분 문자열로 갖는 문자열의 개수가 된다.

 

 

 

#include <stdio.h>
#include <iostream>
using namespace std;
struct Node{
    Node *child[26];
    int cnt;
};

Node *root = (Node *)malloc(sizeof(Node));

void init(void) {
    root->cnt = 0;
    for(int i = 0; i < 26; i++)
    {
        root->child[i] = 0;
    }
}

void insert(int buffer_size, char *buf) {

    Node *now = root;
    for(int i = 0; i < buffer_size; i++)
    {
        if(now->child[buf[i]-'a'])
        {
            now = now->child[buf[i]-'a'];
        }
        else
        {
            now->child[buf[i]-'a'] = (Node *)malloc(sizeof(Node));
            now = now->child[buf[i]-'a'];
            for(int j = 0; j < 26; j++)
            {
                now->child[j] = 0;
            }
            now->cnt = 0;
        }
        
        now->cnt += 1;
    }
        
}


int query(int buffer_size, char *buf) {
  
    Node *now = root;
    for(int i = 0; i < buffer_size; i++)
    {
        if(now->child[buf[i]-'a'])
        {
      		now = now->child[buf[i]-'a'];      
        }
        else
        {
            return 0;
        }
    }
    return now->cnt;
}

int main(void) {
	//freopen("input.txt", "r", stdin);
	int TestCase; 
	for (scanf("%d", &TestCase); TestCase--;) {
		int Query_N;
		scanf("%d", &Query_N);
		
		init();
		
		static int tc = 0;
		printf("#%d", ++tc);
		
		for (int i = 1; i <= Query_N; i++) {
			int type; scanf("%d", &type);

			if (type == 1) {
				char buf[15] = { 0, };
				scanf("%s", buf);
				
				int buffer_size = 0;
				while (buf[buffer_size]) buffer_size++;
				
				insert(buffer_size, buf);
			}
			else {
				char buf[15] = { 0, };
				scanf("%s", buf);
				
				int buffer_size = 0;
				while (buf[buffer_size]) buffer_size++;

				printf(" %d", query(buffer_size, buf));
			}
		}
		printf("\n");
		fflush(stdout);
	}
}