TWpower Reading time ~1 minute

Dump packets using tcpdump command and open it using wireshark


Environment and Prerequisite

  • Linux base system
  • Bash shell(/bin/bash)
  • tcpdump command
  • Wireshark


tcpdump command

What is tcpdump command?

tcpdump [ -AdDefIKlLnNOpqRStuUvxX ] [ -B buffer_size ] [ -c count ]

[ -C file_size ] [ -G rotate_seconds ] [ -F file ]
[ -i interface ] [ -m module ] [ -M secret ]
[ -r file ] [ -s snaplen ] [ -T type ] [ -w file ]
[ -W filecount ]
[ -E spi@ipaddr algo:secret,... ]
[ -y datalinktype ] [ -z postrotate-command ] [ -Z user ] [ expression ]
  • tcpdump: prints out a description of the contents of packets on a network interface with various options.
  • It scans all packets on network so it needs root privilege


Save specific interface’s packets as file

Basic usage

  • -i [inferface name]: give interface name as option
  • -w [file name]: give file name as option
tcpdump -i [interface name] -w [file name]

Example

  • Save eth0 interface’s packets as test.pcap
  • pcap: packet captured file format used in wireshark
  • Use Ctrl + C to quit capturing.
$ sudo tcpdump -i eth0 -w test.pcap
tcpdump: listening on eth0, link-type EN10MB (Ethernet), capture size 262144 bytes
860 packets captured
862 packets received by filter
0 packets dropped by kernel


Wireshark

What is wireshark?

  • The world’s foremost and widely-used network protocol analyzer.
  • It lets you see what’s happening on your network at a microscopic level and is the de facto (and often de jure) standard across many commercial and non-profit enterprises, government agencies, and educational institutions.


Open pcap file using wireshark

  • (방법1) Drag-and-drop is also possible
  • (방법2) Choose file in File-Open tab


Filtering using ip address

  • If you want to filter specific ip address, then add filter to menu’s “Apply a display filter”

ip address filter

ip.addr==X.X.X.X
ip.src==X.X.X.X
ip.dst==X.X.X.X

AND condition

(ip.src==X.X.X.X) || (ip.dst==X.X.X.X)

OR condition

(ip.src==X.X.X.X) && (ip.dst==X.X.X.X)


Reference

TWpower Reading time ~2 minutes

백그라운드로 명령어를 실행해서 병렬적으로 실행되는 멀티 프로세스 환경을 만들어보자.


환경

  • Linux 기반 시스템
  • Bash shell(/bin/bash)


멀티프로세스? 병렬처리? 멀티스레드? 백그라운드 프로세스?

  • 여기서 진행할 방식은 & 연산자를 이용해 명령어나 쉘스크립트의 내용을 백그라운드로 실행시키는 방식을 사용할 예정입니다.
  • 여기저기 찾아본 결과 & 연산자를 이용하면 해당 명령어나 스크립트는 현재 실행되는 프로세스의 자식 프로세스를 생성하여 새로운 서브쉘에서 실행된다고 합니다.
  • 정확하게 명칭을 멀티프로세스나 멀티스레드라고 부르기 애매하나… 영문 자료들에서 & 연산자를 이용해 자식 프로세스를 만든다고 하여 멀티프로세스라고 이름 지었습니다. 혹시 다른 내용이나 더 정확한 내용을 알고 계시면 자료 첨부와 함께 댓글 달아주시면 감사하겠습니다 :)


리눅스 &(Ampersand) 연산자

& 연산자란?

  • 리눅스 환경에서 명령어를 실행할 때 현재 사용하고 있는 쉘이 아닌 새로운 서브쉘을 생성해서 백그라운드에서 실행할 때 사용하는 명령어입니다.
  • &를 사용해서 명령어나 스크립트를 실행하면 백그라운드로 해당 명령어나 스크립트가 실행되며 쉘에서 다른 작업을 계속 할 수 있습니다.
  • 다음 아래 예제들처럼 원하는 명령어를 다 입력한 후에 &를 붙여주면 됩니다.


& 연산자 예제

  • (예제) sleep을 백그라운드에서 실행하기
$ sleep 10 &
[1] 79287
$ # Type enter to make below result
[1]+  Done                    sleep 10
  • (예제) shell script를 백그라운드에서 실행하기
  • 다음 아래처럼 명령어 > 파일명 & 방식을 이용해 stdout을 로그파일로 남길수도 있습니다.
$ tee test_shell.sh << EOF
> #!/bin/bash
>
> echo 1
> sleep 1
> echo 2
> sleep 1
> echo 3
> EOF
echo 1
sleep 1
echo 2
sleep 1
echo 3
$ ./test_shell.sh > tmp_test_shell.log & # You can redirect stdout to specific file.


(예제) 쉘스크립트 함수를 백그라운드에서 병렬로 사용하기

설명

  • 함수를 만들고 해당 함수에 인자를 전달해서 백그라운드로 돌리는 예제를 작성해보겠습니다.
  • 아래 예제는 배열에 있는 원소들을 인자로 전달하여 랜덤한 값에 따라 sleep을 하는 스크립트입니다. &를 사용하지 않는다면 각각 배열의 원소에 대하여 랜덤한 시간만큼 sleep이 끝날 때까지 순차적으로 기다리겠지만 &를 사용했기 때문에 각각의 작업은 백그라운드에서 따로 진행됩니다.
  • 각각 자식 프로세스들이 잘 생성되고 실행되었는지를 확인하기 위해 배열 원소의 이름으로 로그 파일을 만들었습니다.


코드

test_multi_process.sh

#!/bin/bash

function back_ground_process () {
	# Random number between 10 and 15
	sleep_time=$(($RANDOM*12345%6 + 10))

	echo "${1} will sleep for ${sleep_time} seconds"

	sleep ${sleep_time}

	echo "${1} sleep done!"
}

# array in shell script
arr=("a_worker" "b_worker" "c_worker")

# @ means all elements in array
for i in ${arr[@]}; do
    # run back_ground_process function in background
    # pass element of array as argument
    # make log file
    back_ground_process $i > ~/log_${i}.txt &
done
  • wait라는 명령어를 사용하면 현재 실행된 스크립트에서 생성된 모든 자식 프로세스 및 백그라운드 작업을 기다릴수 있습니다.

test_multi_process.sh(continue)

...
# @ means all elements in array
for i in ${arr[@]}; do
    # run back_ground_process function in background
    # pass element of array as argument
    # make log file
    back_ground_process $i > ~/log_${i}.txt &
done

# wait until all child processes are done
wait

echo "All background processes are done!"


결과

  • 실행하고 바로 로그 파일들을 확인합니다.
  • 쉘 스크립트는 백그라운드로 작업을 각각 돌리고 바로 종료되는걸 볼 수 있습니다.
$ ./test_multi_process.sh
$ cat log_a_worker.txt && cat log_b_worker.txt && cat log_c_worker.txt
a_worker will sleep for 13 seconds
b_worker will sleep for 13 seconds
c_worker will sleep for 10 seconds
  • 15초 정도가 지난후에 로그파일들을 보면 각각의 프로세스가 끝났음을 알 수 있습니다.
$ cat log_a_worker.txt && cat log_b_worker.txt && cat log_c_worker.txt
a_worker will sleep for 13 seconds
a_worker sleep done!
b_worker will sleep for 13 seconds
b_worker sleep done!
c_worker will sleep for 10 seconds
c_worker sleep done!


응용

  • 위와 같이 &를 사용해서 사용하고 싶은 데몬이나 프로세스들을 백그라운드로 실행할 수 있습니다.
  • 예를 들어서 여러개의 컴퓨터에 동시에 접속해서 어떤 파일을 설치하는 명령어들을 백그라운드로 병렬로 실행해서 시간을 단축시킬 수 있으며 현재 쉘에서 특정 프로그램을 실행 시키고 계속 현재 쉘을 사용하고 싶을 때 유용합니다.
  • 추가적으로 쉘 스크립트에서 백그라운드로 멀티 프로세스를 진행시키고 싶을 때 사용이 가능합니다.


참고자료

TWpower Reading time ~3 minutes

Make multi processes environment by parallelly running command in background.


Environment and Prerequisite

  • Linux base system
  • Bash shell(/bin/bash)


Multi Process? Parallel Process? Multi Thread? Background Process?

  • In this post, I will run command or shell script in background by using & operator.
  • By searching, found that by using & operator it will make new child process(in new sub-shell) and run command or shell script in that process(in sub-shell)
  • Specifically, it is ambiguous that call above method as multi process or multi thread… However some of english materials said that & operator makes new child process so I call it as multi process in this post’s title. If there is anyone who know well about this, it is pleasure to give a comment.


Linux &(Ampersand) Opearator

What is & operator?

  • In linux, this operator make shell to run the command in the background, that is, it is forked and run in a separate sub-shell, as a job, asynchronously
  • Running command or script using &, that process will be run in background so that it is possible to keep doing other things in current shell.
  • Examples are below. Just add & to end of command.


& operator examples

  • (Example) Run sleep in background
$ sleep 10 &
[1] 79287
$ # Type enter to make below result
[1]+  Done                    sleep 10
  • (Example) Run shell script in background
  • Like below you can make stdout to log file by using command > filename &.
$ tee test_shell.sh << EOF
> #!/bin/bash
>
> echo 1
> sleep 1
> echo 2
> sleep 1
> echo 3
> EOF
echo 1
sleep 1
echo 2
sleep 1
echo 3
$ ./test_shell.sh > tmp_test_shell.log & # You can redirect stdout to specific file.


(Example) Run shell script function in background parallelly

Explanation

  • Make function and run that function with argument in background.
  • Below example script shows that main script pass array’s element to function and sleeps depends on random value . If there is no & operator then it will be run sequentially but if there is & operator then each process will be run in background separately.
  • Add log file to check each child process is run well.


Code

test_multi_process.sh

#!/bin/bash

function back_ground_process () {
	# Random number between 10 and 15
	sleep_time=$(($RANDOM*12345%6 + 10))

	echo "${1} will sleep for ${sleep_time} seconds"

	sleep ${sleep_time}

	echo "${1} sleep done!"
}

# array in shell script
arr=("a_worker" "b_worker" "c_worker")

# @ means all elements in array
for i in ${arr[@]}; do
    # run back_ground_process function in background
    # pass element of array as argument
    # make log file
    back_ground_process $i > ~/log_${i}.txt &
done
  • wait command wait until all child processes(which are made in current script) are done.

test_multi_process.sh(continue)

...
# @ means all elements in array
for i in ${arr[@]}; do
    # run back_ground_process function in background
    # pass element of array as argument
    # make log file
    back_ground_process $i > ~/log_${i}.txt &
done

# wait until all child processes are done
wait

echo "All background processes are done!"


Result

  • Check logs immediately after running script
  • We can notice that script is finished just after running the script
$ ./test_multi_process.sh
$ cat log_a_worker.txt && cat log_b_worker.txt && cat log_c_worker.txt
a_worker will sleep for 13 seconds
b_worker will sleep for 13 seconds
c_worker will sleep for 10 seconds
  • After 15 seconds, we can notice that all child processes are done well.
$ cat log_a_worker.txt && cat log_b_worker.txt && cat log_c_worker.txt
a_worker will sleep for 13 seconds
a_worker sleep done!
b_worker will sleep for 13 seconds
b_worker sleep done!
c_worker will sleep for 10 seconds
c_worker sleep done!


Applications

  • Use & to run process or daemon in background.
  • For example, you can minimize time for installing some files to multi server computers by running in background simultaneously and it is useful when keep using shell while running other programs in same shell.
  • Additionally, you can use it for multi processing or threading in shell script.


References

TWpower Reading time ~7 minutes

C++에서 트라이(Trie)를 구현해보고 기본 문제를 풀어보자.


환경

  • C++


트라이(Trie)란?

트라이(Trie)의 형태 대해서

  • Trie: 트라이(Trie)란 문자열을 저장하고 효율적으로 탐색하기 위한 트리 형태의 자료구조입니다.
  • 위에 보이는 트리의 루트에서부터 자식들을 따라가면서 생성된 문자열들이 트라이 자료구조에 저장되어 있다고 볼 수 있습니다. 저장된 단어는 끝을 표시하는 변수를 추가해서 저장된 단어의 끝을 구분할 수 있습니다.
  • DFS 형태로 검색을 해보면 사진의 번호에 나와있듯이 to, tea, ted, ten, A, i, in, inn이라는 단어들이 자료구조에 들어가 있음을 알 수 있습니다.


트라이(Trie)의 예시

  • 직접 그린 Trie이며 주황색으로 된 노드들이 입력된 문자열들입니다.
  • 현재 be, bee, can, cat, cd가 들어가 있습니다.


사용목적

목적

  • 사용하는 이유는 문자열의 탐색을 하고자할 때 시간복잡도를 보면 알 수 있습니다. 단순하게 하나씩 비교하면서 탐색을 하는것보다 훨씬 효율적입니다. 단, 빠르게 탐색이 가능하다는 장점이 있지만 각 노드에서 자식들에 대한 포인터들을 배열로 모두 저장하고 있다는 점에서 저장 공간의 크기가 크다는 단점도 있습니다.
  • 검색어 자동완성, 사전에서 찾기 그리고 문자열 검사 같은 부분에서 사용할 수 있다고 첨부된 자료에 나와있습니다.

시간 복잡도

  • 제일 긴 문자열의 길이를 L 총 문자열들의 수를 M이라 할 때 시간복잡도는 아래와 같습니다.
  • 생성시 시간복잡도: O(M*L), 모든 문자열들을 넣어야하니 M개에 대해서 트라이 자료구조에 넣는건 가장 긴 문자열 길이만큼 걸리니 L만큼 걸려서 O(M*L)만큼 걸립니다. 물론 삽입 자체만은 O(L)만큼 걸립니다.
  • 탐색시 시간복잡도: O(L), 트리를 타고 들어가봤자 가장 긴 문자열의 길이만큼만 탐색하기 때문에 O(L)만큼 걸립니다.


트라이(Trie)의 구현

공통

  • 알파벳 대문자를 기준으로 만들었습니다.
#include <cstdio>
#include <cstring>

#define ALPHABETS 26

// Convert char to array index
// All are base on capital
int char_to_index(char c){
	return c - 'A';
}


트라이(Trie) 코드

  • is_terminal: 단어의 끝임을 표시하는 변수입니다.
  • void insert(const char * key): 새로운 문자열을 트라이에 추가하는 코드입니다.
  • Trie* find(const char * key): key에 해당하는 문자열을 접두어로 가지고 있는지 확인하고 가지고 있다면 해당 접두어가 끝나는 부분의 위치를 반환합니다.
  • bool string_exist(const char * key): key에 해당하는 문자열이 포함되어 있는지 확인하는 코드입니다. 해당 key의 문자열이 있다면 true를 반환하고 없으면 false를 반환합니다.
struct Trie{

	bool is_terminal; // this represents end of string
	Trie * children[ALPHABETS];

	// Constructor
	Trie(): is_terminal(false){
		memset(children, 0, sizeof(children));
	}

	// Delete all children
	~Trie(){
		for(int i = 0; i < ALPHABETS; ++i){
			if(children[i])
				delete children[i];
		}
	}

	void insert(const char * key){
		if(*key == '\0'){
			is_terminal = true;
		}
		else{
			int index = char_to_index(*key);

			if(children[index] == 0)
				children[index] = new Trie();
			children[index]->insert(key + 1);
		}
	}

	Trie* find(const char * key){
		if(*key == 0){
			return this;
		}

		int index = char_to_index(*key);
		if(children[index] == 0){
			return NULL;
		}

		return children[index]->find(key+1);
	}

	bool string_exist(const char * key){
		if(*key == 0 && is_terminal){
			return true;
		}

		int index = char_to_index(*key);
		if(children[index] == 0){
			return false;
		}
		return children[index]->string_exist(key + 1);
	}

};


메인함수

  • 해당 함수들이 다 올바르게 작동하는지 확인하는 코드를 작성하였습니다.
int main (){

	Trie * root = new Trie();

	const char * words[5] = {"be", "bee", "can", "cat", "cd"};

	for(int i = 0; i < 5; ++i){
		printf("insert: %s\n", words[i]);
		root->insert(words[i]);
	}

	printf("\n");

	printf("%s: be\n", root->find("be") != 0 ? "Prefix Exist" : "Prefix Not Exist");
	printf("%s: can\n", root->find("can") != 0 ? "Prefix Exist" : "Prefix Not Exist");
	printf("%s: a\n", root->find("a") != 0 ? "Prefix Exist" : "Prefix Not Exist");
	printf("%s: cat\n", root->find("cat") != 0 ? "Prefix Exist" : "Prefix Not Exist");
	printf("%s: c\n", root->find("c") != 0 ? "Prefix Exist" : "Prefix Not Exist");

	printf("\n");

	printf("%s: c\n", root->string_exist("c") != 0 ? "String Exist" : "String Not Exist");
	printf("%s: be\n", root->string_exist("be") != 0 ? "String Exist" : "String Not Exist");
	printf("%s: bee\n", root->string_exist("bee") != 0 ? "String Exist" : "String Not Exist");
	printf("%s: candy\n", root->string_exist("candy") != 0 ? "String Exist" : "String Not Exist");
	printf("%s: cd\n", root->string_exist("cd") != 0 ? "String Exist" : "String Not Exist");

	delete root;

	return 0;
}


전체코드

#include <cstdio>
#include <cstring>

#define ALPHABETS 26

// Convert char to array index
// All are base on capital
int char_to_index(char c){
	return c - 'A';
}

struct Trie{

	bool is_terminal; // this represents end of string
	Trie * children[ALPHABETS];

	// Constructor
	Trie(): is_terminal(false){
		memset(children, 0, sizeof(children));
	}

	// Delete all children
	~Trie(){
		for(int i = 0; i < ALPHABETS; ++i){
			if(children[i])
				delete children[i];
		}
	}

	void insert(const char * key){
		if(*key == '\0'){
			is_terminal = true;
		}
		else{
			int index = char_to_index(*key);

			if(children[index] == 0)
				children[index] = new Trie();
			children[index]->insert(key + 1);
		}
	}

	Trie* find(const char * key){
		if(*key == 0){
			return this;
		}

		int index = char_to_index(*key);
		if(children[index] == 0){
			return NULL;
		}

		return children[index]->find(key+1);
	}

	bool string_exist(const char * key){
		if(*key == 0 && is_terminal){
			return true;
		}

		int index = char_to_index(*key);
		if(children[index] == 0){
			return false;
		}
		return children[index]->string_exist(key + 1);
	}

};

int main (){

	Trie * root = new Trie();

	const char * words[5] = {"be", "bee", "can", "cat", "cd"};

	for(int i = 0; i < 5; ++i){
		printf("insert: %s\n", words[i]);
		root->insert(words[i]);
	}

	printf("\n");

	printf("%s: be\n", root->find("be") != 0 ? "Prefix Exist" : "Prefix Not Exist");
	printf("%s: can\n", root->find("can") != 0 ? "Prefix Exist" : "Prefix Not Exist");
	printf("%s: a\n", root->find("a") != 0 ? "Prefix Exist" : "Prefix Not Exist");
	printf("%s: cat\n", root->find("cat") != 0 ? "Prefix Exist" : "Prefix Not Exist");
	printf("%s: c\n", root->find("c") != 0 ? "Prefix Exist" : "Prefix Not Exist");

	printf("\n");

	printf("%s: c\n", root->string_exist("c") != 0 ? "String Exist" : "String Not Exist");
	printf("%s: be\n", root->string_exist("be") != 0 ? "String Exist" : "String Not Exist");
	printf("%s: bee\n", root->string_exist("bee") != 0 ? "String Exist" : "String Not Exist");
	printf("%s: candy\n", root->string_exist("candy") != 0 ? "String Exist" : "String Not Exist");
	printf("%s: cd\n", root->string_exist("cd") != 0 ? "String Exist" : "String Not Exist");

	delete root;

	return 0;
}


트라이(Trie)를 이용한 기본 문제

백준 온라인 저지 5052번

  • 전화번호 목록이 주어질 때 해당 번호들이 일관성이 있는지 확인하는 코드로 일관성이 있으면 YES를 없으면 NO를 출력하는 문제
  • 전화번호 목록들 중에 어떠한 번호가 다른 번호의 접두어가 되면 일관성이 없다고 판단한다. 다시 말해 전화번호 목록이 일관성을 유지하려면, 한 번호가 다른 번호의 접두어인 경우가 없어야 한다.
  • 링크: https://www.acmicpc.net/problem/5052


풀이 및 접근

  • 문자열을 처리하는 문제이며 나아가 접두어를 이용한 자료구조를 만들어야하기 때문에 트라이(Trie)를 사용해야함을 알 수 있습니다.
  • 방법1: 트라이에 모든 번호들을 저장하고 탐색하면서 문자열이 끝나기전에 is_terminal이 나오면 접두어가 존재하는 것이기 때문에 false를 반환해서 판단해줍니다.
  • 방법2: 트라이에 번호들을 추가하면서 현재 주어진 번호가 다른 번호의 접두어가 되는지 바로 판단합니다.


풀이 코드

방법1

  • 트라이에 모든 번호들을 저장하고 탐색하면서 문자열이 끝나기전에 is_terminal이 나오면 접두어가 존재하는 것이기 때문에 false를 반환해서 판단해줍니다.
#include <cstdio>
#include <cstring>

int char_to_index(char c){
	return c - '0';
}

struct Trie {

	bool is_terminal;
	Trie * next[10];
	Trie(): is_terminal(false) {
		memset(next, 0, sizeof(next));
	}

	~Trie() {
		for (int i = 0; i < 10; ++i) {
			if (next[i]) {
				delete next[i];
			}
		}
	}

	void insert(const char * key) {

		if (*key == '\0') {
			is_terminal = true;
		}
		else {
			int index = char_to_index(*key);
			if (next[index] == 0)
				next[index] = new Trie();
			next[index]->insert(key + 1);
		}
	}

	bool find(const char * key) {

		if (*key == '\0') return true;

		// Return false if there is already terminal node before string is the end.
		if (is_terminal) return false;

		int index = char_to_index(*key);
		return next[index]->find(key + 1);
	}
};

int main() {

	int t;
	char phone_books[10000][11];
	scanf("%d", &t);

	while (t--) {
		int n;
		scanf("%d", &n);

		Trie * root = new Trie();
		for (int i = 0; i < n; ++i) {
			scanf("%s", &phone_books[i]);
			root->insert(phone_books[i]);
		}

		bool is_valid = true;
		for (int i = 0; i < n; ++i) {

			if (root->find(phone_books[i]) == false) {
				is_valid = false;
				break;
			}
		}
        delete root;
		printf("%s\n", is_valid ? "YES" : "NO");
	}
	return 0;
}

방법2

  • 트라이에 번호들을 추가하면서 현재 주어진 번호가 다른 번호의 접두어가 되는지 바로 판단합니다.
#include <cstdio>
#include <cstring>

int char_to_index(char c){
	return c - '0';
}

struct Trie {

	bool is_terminal;
	Trie * next[10];

	Trie(): is_terminal(false) {
		memset(next, 0, sizeof(next));
	}

	~Trie() {
		for (int i = 0; i < 10; ++i) {
			if (next[i]) {
				delete next[i];
			}
		}
	}

	bool insert(const char * key) {

		if (*key == '\0') {
			is_terminal = true;
			return true;
		}
		else {
			// If it is already terminal node then there is a prefix match
			if(is_terminal == true) return false;

			int index = char_to_index(*key);

			if (next[index] == 0)
				next[index] = new Trie();

			// If next node is already exists and current's next is end of string then there is a prefix match
			else if(next[index] != 0 && *(key + 1) == '\0'){
				return false;
			}
			return next[index]->insert(key + 1);
		}
	}
};

int main() {

	int t;
	char phone_books[10000][11];
	scanf("%d", &t);

	while (t--) {
		int n;
		scanf("%d", &n);

		Trie * root = new Trie();

		bool ret = true;

		for (int i = 0; i < n; ++i) {
			scanf("%s", &phone_books[i]);

			if (ret == false) continue;

			ret = root->insert(phone_books[i]);

		}

		delete root;
		printf("%s\n", ret ? "YES" : "NO");
	}
	return 0;
}


참고자료

TWpower Reading time ~7 minutes

Implement trie and solve basic problem in C++.


Environment and Prerequisite

  • C++


What is Trie?

About Trie

  • Trie: Trie is a tree shape data structure for efficiently searching and storing strings.
  • From root to leaf nodes are strings which stored in trie data structure. We can distinguish end of string by adding terminal variable to each node.
  • By searching DFS method in above picture, we can find that to, tea, ted, ten, A, i, in, inn strings are stored in data structure.


Example of Trie

  • Orange color nodes are inserted strings.
  • be, bee, can, cat, cd are stored in trie.


Purpose of Trie

Purpose

  • The reason why we use trie is in time complexity of string searching. It is much more efficient than linear searching. However there is advantage that searching is efficient but also drawbacks that it saves all children pointer in each node so trie takes many spaces.
  • It can be used in searching keyword autocomplete, searching in dictionary and spelling checking. Reference is in References

Time Complexity

  • Consider L as longest string and M as total number of strings.
  • Creation time complexity: O(M*L), There are total M strings and each string only takes at most L time so it takes O(M*L). Insertion itself takes O(L).
  • Searching time complexity: O(L), It takes at most O(L) of time. Because it is tree structure.


Trie Implementation

Common

  • Only consider capital alphabets
#include <cstdio>
#include <cstring>

#define ALPHABETS 26

// Convert char to array index
// All are base on capital
int char_to_index(char c){
	return c - 'A';
}


Trie Code

  • is_terminal: It represents end of string.
  • void insert(const char * key): Add new string to trie structure.
  • Trie* find(const char * key): Check if trie has key(passed string argument) as prefix. If it has key as prefix then return end of key prefix node.
  • bool string_exist(const char * key): Check if trie has key(passed string argument). If it has key then return true. If not then return false.
struct Trie{

	bool is_terminal; // this represents end of string
	Trie * children[ALPHABETS];

	// Constructor
	Trie(): is_terminal(false){
		memset(children, 0, sizeof(children));
	}

	// Delete all children
	~Trie(){
		for(int i = 0; i < ALPHABETS; ++i){
			if(children[i])
				delete children[i];
		}
	}

	void insert(const char * key){
		if(*key == '\0'){
			is_terminal = true;
		}
		else{
			int index = char_to_index(*key);

			if(children[index] == 0)
				children[index] = new Trie();
			children[index]->insert(key + 1);
		}
	}

	Trie* find(const char * key){
		if(*key == 0){
			return this;
		}

		int index = char_to_index(*key);
		if(children[index] == 0){
			return NULL;
		}

		return children[index]->find(key+1);
	}

	bool string_exist(const char * key){
		if(*key == 0 && is_terminal){
			return true;
		}

		int index = char_to_index(*key);
		if(children[index] == 0){
			return false;
		}
		return children[index]->string_exist(key + 1);
	}

};


Main Function

  • Add check code in main function.
  • Main function checks whether trie works well.
int main (){

	Trie * root = new Trie();

	const char * words[5] = {"be", "bee", "can", "cat", "cd"};

	for(int i = 0; i < 5; ++i){
		printf("insert: %s\n", words[i]);
		root->insert(words[i]);
	}

	printf("\n");

	printf("%s: be\n", root->find("be") != 0 ? "Prefix Exist" : "Prefix Not Exist");
	printf("%s: can\n", root->find("can") != 0 ? "Prefix Exist" : "Prefix Not Exist");
	printf("%s: a\n", root->find("a") != 0 ? "Prefix Exist" : "Prefix Not Exist");
	printf("%s: cat\n", root->find("cat") != 0 ? "Prefix Exist" : "Prefix Not Exist");
	printf("%s: c\n", root->find("c") != 0 ? "Prefix Exist" : "Prefix Not Exist");

	printf("\n");

	printf("%s: c\n", root->string_exist("c") != 0 ? "String Exist" : "String Not Exist");
	printf("%s: be\n", root->string_exist("be") != 0 ? "String Exist" : "String Not Exist");
	printf("%s: bee\n", root->string_exist("bee") != 0 ? "String Exist" : "String Not Exist");
	printf("%s: candy\n", root->string_exist("candy") != 0 ? "String Exist" : "String Not Exist");
	printf("%s: cd\n", root->string_exist("cd") != 0 ? "String Exist" : "String Not Exist");

	delete root;

	return 0;
}


All codes

#include <cstdio>
#include <cstring>

#define ALPHABETS 26

// Convert char to array index
// All are base on capital
int char_to_index(char c){
	return c - 'A';
}

struct Trie{

	bool is_terminal; // this represents end of string
	Trie * children[ALPHABETS];

	// Constructor
	Trie(): is_terminal(false){
		memset(children, 0, sizeof(children));
	}

	// Delete all children
	~Trie(){
		for(int i = 0; i < ALPHABETS; ++i){
			if(children[i])
				delete children[i];
		}
	}

	void insert(const char * key){
		if(*key == '\0'){
			is_terminal = true;
		}
		else{
			int index = char_to_index(*key);

			if(children[index] == 0)
				children[index] = new Trie();
			children[index]->insert(key + 1);
		}
	}

	Trie* find(const char * key){
		if(*key == 0){
			return this;
		}

		int index = char_to_index(*key);
		if(children[index] == 0){
			return NULL;
		}

		return children[index]->find(key+1);
	}

	bool string_exist(const char * key){
		if(*key == 0 && is_terminal){
			return true;
		}

		int index = char_to_index(*key);
		if(children[index] == 0){
			return false;
		}
		return children[index]->string_exist(key + 1);
	}

};

int main (){

	Trie * root = new Trie();

	const char * words[5] = {"be", "bee", "can", "cat", "cd"};

	for(int i = 0; i < 5; ++i){
		printf("insert: %s\n", words[i]);
		root->insert(words[i]);
	}

	printf("\n");

	printf("%s: be\n", root->find("be") != 0 ? "Prefix Exist" : "Prefix Not Exist");
	printf("%s: can\n", root->find("can") != 0 ? "Prefix Exist" : "Prefix Not Exist");
	printf("%s: a\n", root->find("a") != 0 ? "Prefix Exist" : "Prefix Not Exist");
	printf("%s: cat\n", root->find("cat") != 0 ? "Prefix Exist" : "Prefix Not Exist");
	printf("%s: c\n", root->find("c") != 0 ? "Prefix Exist" : "Prefix Not Exist");

	printf("\n");

	printf("%s: c\n", root->string_exist("c") != 0 ? "String Exist" : "String Not Exist");
	printf("%s: be\n", root->string_exist("be") != 0 ? "String Exist" : "String Not Exist");
	printf("%s: bee\n", root->string_exist("bee") != 0 ? "String Exist" : "String Not Exist");
	printf("%s: candy\n", root->string_exist("candy") != 0 ? "String Exist" : "String Not Exist");
	printf("%s: cd\n", root->string_exist("cd") != 0 ? "String Exist" : "String Not Exist");

	delete root;

	return 0;
}


Trie Basic Problem

Baekjoon Online Judge 5052

  • Check if phone number list is in consistency. Print YES if it is in consistency if not then print NO.
  • In consistency means that any number is not prefix to other numbers.
  • Link: https://www.acmicpc.net/problem/5052


Solution and Method

  • It is string processing problem and also it contains prefix processing so using trie data structure is solution.
  • Solution 1: Insert all phone numbers to trie and search all phone numbers. If there is terminal node(is_terminal value is true) before end of the phone number, then return false.
  • Solution 2: Check inserted phone number is prefix to other numbers when insert into trie.


Solution Codes

Solution 1

  • Insert all phone numbers to trie and search all phone numbers. If there is terminal node(is_terminal value is true) before end of the phone number, then return false.
#include <cstdio>
#include <cstring>

int char_to_index(char c){
	return c - '0';
}

struct Trie {

	bool is_terminal;
	Trie * next[10];
	Trie(): is_terminal(false) {
		memset(next, 0, sizeof(next));
	}

	~Trie() {
		for (int i = 0; i < 10; ++i) {
			if (next[i]) {
				delete next[i];
			}
		}
	}

	void insert(const char * key) {

		if (*key == '\0') {
			is_terminal = true;
		}
		else {
			int index = char_to_index(*key);
			if (next[index] == 0)
				next[index] = new Trie();
			next[index]->insert(key + 1);
		}
	}

	bool find(const char * key) {

		if (*key == '\0') return true;

		// Return false if there is already terminal node before string is the end.
		if (is_terminal) return false;

		int index = char_to_index(*key);
		return next[index]->find(key + 1);
	}
};

int main() {

	int t;
	char phone_books[10000][11];
	scanf("%d", &t);

	while (t--) {
		int n;
		scanf("%d", &n);

		Trie * root = new Trie();
		for (int i = 0; i < n; ++i) {
			scanf("%s", &phone_books[i]);
			root->insert(phone_books[i]);
		}

		bool is_valid = true;
		for (int i = 0; i < n; ++i) {

			if (root->find(phone_books[i]) == false) {
				is_valid = false;
				break;
			}
		}
        delete root;
		printf("%s\n", is_valid ? "YES" : "NO");
	}
	return 0;
}

Solution 2

  • Check inserted phone number is prefix to other numbers when insert into trie.
#include <cstdio>
#include <cstring>

int char_to_index(char c){
	return c - '0';
}

struct Trie {

	bool is_terminal;
	Trie * next[10];

	Trie(): is_terminal(false) {
		memset(next, 0, sizeof(next));
	}

	~Trie() {
		for (int i = 0; i < 10; ++i) {
			if (next[i]) {
				delete next[i];
			}
		}
	}

	bool insert(const char * key) {

		if (*key == '\0') {
			is_terminal = true;
			return true;
		}
		else {
			// If it is already terminal node then there is a prefix match
			if(is_terminal == true) return false;

			int index = char_to_index(*key);

			if (next[index] == 0)
				next[index] = new Trie();

			// If next node is already exists and current's next is end of string then there is a prefix match
			else if(next[index] != 0 && *(key + 1) == '\0'){
				return false;
			}
			return next[index]->insert(key + 1);
		}
	}
};

int main() {

	int t;
	char phone_books[10000][11];
	scanf("%d", &t);

	while (t--) {
		int n;
		scanf("%d", &n);

		Trie * root = new Trie();

		bool ret = true;

		for (int i = 0; i < n; ++i) {
			scanf("%s", &phone_books[i]);

			if (ret == false) continue;

			ret = root->insert(phone_books[i]);

		}

		delete root;
		printf("%s\n", ret ? "YES" : "NO");
	}
	return 0;
}


References