트라이는 다음과 같은 특징이 있다.

• 검색이 빠른 특성을 갖는다.
• retrieval(검색)에서 유래. (by Edward Fredkin)
• digital tree 혹은 prefix tree라고도 불림.
• 스트링을 키로하는 동적 집합(dynamic set)이나 연관 배열(associative array)로 사용됨.
• 이진 검색 트리와는 달리, 노드는 키를 갖지 않는 대신, 그 위치가 키 역할을 한다.
• root는 빈 스트링이다.
• 한 노드와 연관된 스트링은 그 하위 노드의 공통 접두어가 된다.
• 연관을 갖지 않는 노드가 있을 수 있다.

이진 검색 트리와 트라이의 시간 복잡도.

• 문자열은 정수와 실수와는 달리 그 길이가 변하기 때문에 검색에 시간이 많이 걸린다.
• 길이가 고정된 정수나 실수의 경우 이진 트리에서 O(logN) 이지만
  • 왜냐면 이진 트리에서는 한 번 검색할 때마다 검색할 대상이 반으로 줄기 때문.
• 문자열은 길이가 변하기 때문에 문자열의 최대 길이 M을 곱합 O(MlogN)이 된다.
• 트라이는 이런 문제를 해결하기 위해 고안된 자료 구조이다.

문자열 집합 : S = {“BE”, “BET”, “BUS”, “TEA”, “TEN”} 의 트라이 구성

• 루트는 빈 노드.
• 부모 노드에 접미 문자 하나씩을 붙여서 자식 노드를 만든다.
• 간선은 접미 문자가 붙는 것을 나타냄.
• 회색 노드는 종료 노드.
• 루트에서 해당 종료 노드까지의 문자를 모으면 검색어 발견.

// 알파벳 소문자를 저장하는 경우 각 노드는 26개의 자손을 가질 수 있다
const int ALPHABETS = 26;
int toNumber(char ch) { return ch - 'A'; }
 
struct LinkedListNode {
 
	int elem;
	LinkedListNode* next;
 
	LinkedListNode(int _elem, LinkedListNode* _next) : elem(_elem), next(_next) {
	}
 
};
 
// 트라이의 한 노드를 나타내는 객체
struct TrieNode {
	TrieNode* children[ALPHABETS];
	// 이 노드가 종료 노드인가?
	bool terminal;
 
	TrieNode() : terminal(false) {
		memset(children, 0, sizeof(children));
	}
 
	~TrieNode() {
		for(int i = 0; i < ALPHABETS; i++)
			if(children[i])
				delete children[i];
	}
 
	// 이 노드를 루트로 하는 트라이에 문자열 key 를 추가한다.
	void insert(const char* key) {
		// 문자열이 끝나면 terminal 만 참으로 바꾸고 종료
		if(*key == 0)
			terminal = true;
		else {
			int next = toNumber(*key);
			// 해당 자식 노드가 없다면 생성한다
			if(children[next] == NULL)
				children[next] = new TrieNode();
			// 해당 자식 노드로 재귀호출
			children[next]->insert(key + 1);
		}
	}
 
	// 이 노드를 루트로 하는 트라이에 문자열 key 와 대응되는 노드를 찾는다.
	// 없으면 NULL 을 반환한다.
	TrieNode* find(const char* key) {
		if(*key == 0) return this;
		int next = toNumber(*key);
		if(children[next] == NULL) return NULL;
		return children[next]->find(key+1);
	}
};

; 맵으로 노드 표현
; {:id 정수 문자 {...} 문자 {...} ...}
; :id 는 현재 노드가 중간 노드인지 아니면 종료 노드인지 표시
; 이후 자식에 해당하는 문자를 키로 하고 해당 자식 노드를 값으로 한다.
 
(defn find-word [trie word]
  (get-in trie (seq word)))
 
(defn insert-word [trie word]
  (reduce #(if (get-in % %2) 
               %
               (assoc-in % %2 {:id (if (= (count word) (count %2)) 1 0)}))
          trie
          (reduce #(conj % (str (last %) %2)) [] (seq word))))
 
(defn make-trie [col]
  (reduce insert-word {} col))
 
(def trie (make-trie ["BUS" "BE" "BET" "TEA" "TEN"]))
 
trie
;=> {:id 0 \B {:id 0 \U {:id 0 \S {:id 1}} \E {:id 1 \T {:id 1}}} \T {:id 0 \E {:id 0 \A {:id 1} \N {:id 1}}}}
 
(find-word trie "BUS")
;=> {:id 1}
(find-word trie "BE")
;=> {\T {:id 1}, :id 1}
(find-word trie "TE")
;=> {\A {:id 1}, \N {:id 1}, :id 0}

위 C++ 코드에서 terminal을 불린형에서 정수형으로 바꾸면 사전 자료 구조로 사용할 수 있다. terminal을 정수로 바꾸면 map<string, int> 형의 사전 자료 구조가 된다.

한 문자열 S의 모든 접미사를 트라이에 넣는 것을 말한다. 이렇게 해서 부분 문자열을 빠르게 검색할 수 있다.

• 문자 입력이 불편한 핸드폰이나 타블렛을 위한 자동 완성기
• 자동 완성 알고리즘은 사전에 저장된 N개의 단어들을 이용한다.
• 타이핑을 하면 입력된 문자들로 시작하는 사전내 단어을 추천.
• 추천은 가장 출현 빈도가 높고, 알파벳 순으로.
• 탭을 누르면 추천된 단어가 자동으로 입력.

• 입력의 첫 줄은 테스트 케이스의 수 C (1 ⇐ C ⇐ 10)
• 각 테스트의 첫 줄은 2 개의 숫자가 있다.
  • 사전에 포함된 단어의 수 N (1 ⇐ N ⇐ 10000)
  • 입력할 단어의 수 M (1 ⇐ M ⇐ 20000)
• 이 후 문자열과 출현 빈도로 된 N 개의 줄
  • 1 ⇐ 출현 빈도 ⇐ 10
• 마지막 줄에 M개의 단어로 된 문자열
• 단, 단어는 모두 알파벳 대문자이고, 길이는 최대 10

*inp 파일

2
7 8
ALL 4
AND 3
FISH 8
FOR 6
SO 4
THANKS 9
THE 9
SO LONG AND THANKS FOR ALL THE FISH
7 8
ALL 4
AND 5
FISH 3
FOR 6
SO 8
THANKS 1
THE 2
SO LONG AND THANKS FOR ALL THE FISH

• 메모리 : 64MB 이하
• 시간 : 3 sec 이내

(ns trie
  (:use [clojure.string :only [split]]
        [clojure.java.io])
  (:import [java.io BufferedReader StringReader]))
 
(defn recommend [dic prefix]
  (let [sv (filter #(.startsWith % prefix) (keys dic))]
    (sort
      (reduce (fn [col s] 
               (let [n (dic s)
                     k (dic (first col))]
                 (cond
                   (nil? k) (conj col s)
                   (< n k)  col
                   (= n k)  (conj col s)
                   (> n k)  (conj [] s))))                   
              []
              sv))))
 
 
(defn count-typing [dic word]
  (some #(let [r (recommand dic %)]
              (cond
                (empty? r) (count word)
                (= (first r) word) (if (= % word) (count %) (inc (count %)))
                :else nil))
          (reduce #(conj % (str (last %) %2)) [] (seq word))))
 
(defn count-min-typings [dic sentence]
  (let [s (split sentence #"\s")]
    (reduce #(+ % (count-typing dic %2)) 0 s)))
 
(defn make-dic [lines]
  (reduce (fn [col [k v]] (assoc col k (read-string v)))
          {} 
          (map #(split % #"\s") lines)))
 
(defn try-case [rdr]
  (let [[wc1 wc2] (map read-string (split (.readLine rdr) #"\s"))
        dic (make-dic (take wc1 (line-seq rdr)))
        input-string (.readLine rdr)]
      (+ (dec wc2) (count-min-typings dic input-string))))
 
(defn solve [input]
  (let [rdr (BufferedReader. (StringReader. input))
        case-count (read-string (.readLine rdr))]
    (for [n (range case-count)]
      (try-case rdr))))
 
(solve (slurp "inp"))
;=> (28 29)

(ns solong
  (:use [clojure.string :only [split]]
        [clojure.java.io])
  (:import [java.io BufferedReader StringReader]))
 
(defn find-word [trie word]
  (get-in trie (seq word)))
 
(defn insert-word [trie [word freq]]
  (reduce #(if (get-in % %2) 
               %
               (assoc-in % %2 {:id (if (= (count word) (count %2)) freq 0)}))
          trie
          (reduce #(conj % (str (last %) %2)) [] (seq word))))
 
(defn make-trie [lines]
  (reduce insert-word {} 
          (map #(let [[k v] (split % #"\s")] [k (read-string v)]) lines)))
 
(defn children [trie]
  (keys (dissoc trie :id)))
 
(defn iterate-children [trie]
  (let [t (fn [col]
              (mapcat #(map (fn [c] (conj % c)) (children (get-in trie %))) 
              col))]
  (take-while seq (iterate t (map vector (children trie))))))
 
(defn find-prefix [trie col]
  (let [trie (get-in trie col)]
    (if (and (:id trie) (nil? (children trie))) 
        (list col)
        (map #(concat col %) 
             (apply concat (iterate-children trie))))))
 
(defn recommend [trie col]
  (apply str (first (sort-by 
                       (juxt #(- ((get-in trie %) :id)) #(apply str %)) 
                       (find-prefix trie (seq col))))))
 
(defn count-typing [trie word]
  (some #(let [r (recommand trie %)]
              (cond
                (empty? r) (count word)
                (= r word) (if (= % word) (count %) (inc (count %)))
                :else nil))
          (reduce #(conj % (str (last %) %2)) [] (seq word))))
 
(defn count-min-typings [trie sentence]
  (let [s (split sentence #"\s")]
    (reduce #(+ % (count-typing trie %2)) 0 s)))
 
(defn try-case [rdr]
  (let [[wc1 wc2] (map read-string (split (.readLine rdr) #"\s"))
        trie (make-trie (take wc1 (line-seq rdr)))
        input-string (.readLine rdr)]
      (+ (dec wc2) (count-min-typings trie input-string))))
 
(defn solve [input]
  (let [rdr (BufferedReader. (StringReader. input))
        case-count (read-string (.readLine rdr))]
    (for [n (range case-count)]
      (try-case rdr))))
 
(solve (slurp "inp"))
;=> (28 29)

#include<algorithm>
#include<cstring>
#include<cstdio>
#include<iostream>
#include<string>
#include<vector>
using namespace std;
 
// 알파벳 소문자를 저장하는 경우 각 노드는 26개의 자손을 가질 수 있다
const int ALPHABETS = 26;
int toNumber(char ch) { return ch - 'A'; }
 
// 트라이의 한 노드를 나타내는 객체
struct TrieNode {
	TrieNode* children[ALPHABETS];
	// 이 노드에서 종료하는 문자열의 번호
	int terminal;
	// 이 노드를 루트로 하는 트라이에 가장 먼저 추가된 단어의 번호
	int first;
 
	TrieNode() {
		memset(children, 0, sizeof(children));
		terminal = first = -1;
	}
 
	~TrieNode() {
		for(int i = 0; i < ALPHABETS; i++)
			if(children[i])
				delete children[i];
	}
 
	// 이 노드를 루트로 하는 트라이에 번호 id 인 문자열 key 를 추가한다
	void insert(const char* key, int id) {
		// first 를 우선 업데이트
		if(first == -1) first = id;
 
		// 문자열이 끝났다면 terminal 만 바꾸고 종료
		if(*key == 0)
			terminal = id;
		else {
			int next = toNumber(*key);
			// 해당 자식 노드가 없다면 생성한다
			if(children[next] == NULL)
				children[next] = new TrieNode();
			// 해당 자식 노드로 재귀호출
			children[next]->insert(key + 1, id);
		}
	}
 
	// 이 노드까지 타이핑해 왔을 때, 번호 id 인 key 를 타이핑하기 위해
	// 최소 몇 번의 키를 더 눌러야 하나?
	int type(const char* key, int id) {
		// 문자열 종료시
		if(*key == 0) return 0;
 
		// 이 노드에서 추천되는 문자열이 이 문자열이면 탭 누르고 종료
		if(first == id) return 1;
 
		// 아니면 다음 문자를 타이핑한다
		int next = toNumber(*key);
		return 1 + children[next]->type(key + 1, id);
	}
 
	// 이 노드를 루트로 하는 트라이에 문자열 key 와 대응되는 노드를 찾는다.
	// 없으면 NULL 을 반환한다.
	TrieNode* find(const char* key) {
		if(*key == 0) return this;
		int next = toNumber(*key);
		if(children[next] == NULL) return NULL;
		return children[next]->find(key+1);
	}
};
 
// 사전을 나타내는 트라이가 주어질 때, 단어 word 를 타이핑하는 데
// 몇 번이나 키를 눌러야 하는지 계산한다
int countKeys(TrieNode* trie, const char* word) {
	// 이 문자열이 사전에 있는지 확인하고, 있다면 번호를 구한다
	TrieNode* node = trie->find(word);
	// 사전에 없으면 직접 타이핑할 수밖에 없다
	if(node == NULL || node->terminal == -1) return strlen(word);
	// 탐색하면서 타이핑할 방법을 찾는다
	return trie->type(word, node->terminal);
}
 
// 입력에 주어지는 단어들을 정렬해서 트라이로 변환한다
TrieNode* readInput(FILE *fp, int words) {
	// 단어들을 출현 빈도의 내림차순, 단어의 오름차순으로 정렬한다
	vector<pair<int,string> > input;
	for(int i = 0; i < words; i++) {
		char buf[11];
		int freq;
		fscanf(fp, "%s %d", buf, &freq);
		input.push_back(make_pair(-freq, buf));
	}
	sort(input.begin(), input.end());
	// 이 때 앞에 있는 단어일 수록 우선 순위가 높다.
	// 배열의 인덱스를 각 단어의 번호로 쓰자.
	TrieNode* trie = new TrieNode();
	for(int i = 0; i < input.size(); i++)
		trie->insert(input[i].second.c_str(), i);
	// 아무 문자도 입력하지 않은 상황에서는 자동 완성되지 않아야 한다
	trie->first = -1;
	return trie;
}
 
int main() {
    FILE *fp = fopen("inp", "r");
 
    int cases;
    fscanf(fp, "%d", &cases);
    for(int cc = 0; cc < cases; ++cc) {
    	int n, m;
    	fscanf(fp, "%d %d", &n, &m);
    	TrieNode* trie = readInput(fp, n);
    	int ret = 0;
    	for(int i = 0; i < m; i++) {
    		char buf[11];
    		fscanf(fp, "%s", buf);
    		int add = countKeys(trie, buf);
    		ret += add;
		}
    	delete trie;
    	printf("%d\n", ret + m-1);
    }
}

문제점 :

예제 입력에서 입력 문자열을 받아와서 어떤 문자열을 입력할 지를 미리 파악한 후 그 문자열의 ID로 추천어를 생성하고 있다. 즉 다음과 같다.

1. countKeys 함수에서 word 인자는 이미 예제 입력에서 사용자가 타이핑할 온전한 단어이다.
   • 하지만 사용자가 한 글자씩 타이핑하는 실제 상황에서는 어떤 단어로 완성이 될지 알 수가 없다.
2. 이 word 인자로 find함수를 호출하여 해당 단어의 id를 구한다.
   • 결국 실제 상황에서는 find 함수를 호출할 수가 없다.
3. 이 id와 각 트라이 노드의first를 비교해서 빠르게 추천어를 찾을 수 있다.

하지만 실제 상황에서는 돌고래가 어떤 문자열을 입력하게 될지는 실제로는 알 수 없기 때문에 추천어를 생성하는 로직은 좀 더 복잡해질 것이다.

• readInput
  • 문자열 정렬
    • N개의 문자열 정렬 : O(NlogN)
    • 사전에 포함된 문자열의 최대 길이가 K : O(KNlogN)
  • 트라이 생성
    • 문자열 길이의 총합에 비례 : O(KN)
  • 시간 복잡도 : O(KNlogN)

• countKeys
  • 모든 단어의 길의의 합에 비례 : O(KN)

• 전체 시간 복잡도
  • 타이핑할 문자열의 전체 길이가 L: O(KNlogN+L)

원문에서 여러 개의 문자열을 검색하는 문제에 트라이를 이용할 수 있다.

짚더미 문자열 H : “CACACHEFCACHY” 바늘 문자열 : “CACHE”, “HE”, “CHEF”, “ACHY”

20 장 2 절에 소개됨.

바늘 문자열의 각 접두사마다 이 접두사의 접두사도 되고 접미사도 되는 문자열의 최대 길이 미리 계산

바늘 문자열 : “CACHE” 대응되는 문자열 : “CAC” 이후 실패 이 때 접미사도 되고 접두사도 되는 문자열은 “C” 이다. 그러면 대응되는 문자열은 세 글자가 아니라 한 글자라 생각하고, 다음 “A”부터 찾는다.

            C :접두사도 되고 접미사도 되는 최대 문자열
            _  
           | |
1차매칭:   CACH
           |||x
짚더미:    CACACHEFCACHY
             ||||| 
2차매칭:     CACHE
  

이런 과정때문에 짚더미 문자열의 각 문자를 한 번만 보고 모든 출현 위치를 찾아 낼 수 있다. 대응에 실패했을 때 어디로 가서 검색을 계속해야 할지 알려준다고 해서, 이런 정보를 실패 함수라고 한다.

다음은 네 개의 바늘 문자열 “CACHE”, “HE”, “CHEF”, “ACHY”에 대한 KMP 알고리즘이 생성하는 실패 함수를 보여준다.

위 그림에서 겹치는 접두사를 모아서 다시 그리면…

failure(s) : s 의 접미사이면서 트라이에 포함된 가장 긴 문자열까지 가는 화살표

이와 같은 실패 함수를 전처리 과정에서 만든 뒤, 짚더미 문자열의 글자를 순회하면서 트라이의 상태들을 서로 오가면 모든 바늘 문자열들에 대해 동시에 KMP 알고리즘을 수행하는 것과 같은 효과를 낸다.

이것을 아호-코라식 문자열 검색 알고리즘이라고 부른다. 이 알고리즘은 긴 문서에서 많은 문자열을 동시게 창아야 하는 검색 엔진등에서 특히 유용하게 사용된다.

아호-코라식 알고리즘을 사용하기 위해서는 각 노드마다 다음과 같은 정보를 추가해야 한다.

• 실패 연결(failure link) : 각 노드에서의 실패 함수. 해당 노드에서 다음 글자를 대응하는데 실패했을 때, 다음으로 가서 시도해야 할 노드의 포인터.
• 출력 문자열 목록 : 각 노드에 도달했을 때 어떤 바늘 문자열을 발견하게 되는지를 저장. 한 바늘 문자열이 다른 바늘 문자열의 부분 문자열인 경우, 해당 바늘 문자열이 종료되는 노드 외의 장소에서도 문자열을 발견할 수 있기 때문에 마련된 별도의 목록. 예를 들어 ABC, B, BC 3개의 바늘 문자열이 있다면 상태 AB에 도달했을 때는 바늘 문자열 B를, 상태 ABC에 도달했을 때는 바늘 문자열 ABC와 BC를 발젼할 수 있다.

// 트라이의 한 노드를 나타내는 객체
struct TrieNode {
	TrieNode* children[ALPHABETS];
	// 현 위치에서 끝나는 문자열의 번호
	int terminal;
 
	// 이 노드에서 매칭이 실패했을 때 이 곳으로 가서 계속한다.
	// 이 노드에 대응되는 문자열의 접미사이면서 트라이에 포함된 최대 문자열.
	TrieNode* fail;
	// 이 노드가 방문되었을 때 등장하는 문자열들의 번호
	vector<int> output;
 
	TrieNode() : terminal(-1) {
		memset(children, 0, sizeof(children));
	}
 
	~TrieNode() {
		for(int i = 0; i < ALPHABETS; i++)
			if(children[i])
				delete children[i];
	}
 
	// 이 노드를 루트로 하는 트라이에 번호가 id 인 문자열 key 를 추가한다
	void insert(const char* key, int id) {
		// 문자열이 끝나면 terminal 만 참으로 바꾸고 종료
		if(*key == 0)
			terminal = id;
		else {
			int next = toNumber(*key);
			// 해당 자식 노드가 없다면 생성한다
			if(children[next] == NULL)
				children[next] = new TrieNode();
			// 해당 자식 노드로 재귀호출
			children[next]->insert(key + 1, id);
		}
	}
 
	TrieNode* find(const char* key) {
		if(*key == 0) return this;
		int next = toNumber(*key);
		if(children[next] == NULL) return NULL;
		return children[next]->find(key+1);
	}
};

무식한 방법 : 해당 노드에 대응된 문자열의 모든 접미사들을 하나하나 시도하면서 이 중 트라이에 포함되어 있는 첫 번째 문자열을 찾는 것.

빠른 방법 : 부모 노드의 실패 연결을 이용해서 자식 노드의 실패 연결을 쉽게 알 수 있다.

"CAC"  -> "AC"
"CACH" -> "ACH"

실패 연결을 계산하는 방법:

1. 부모 노드와 자식 노드간에 간선 X로 연결되어 있을 때, 부모 노드의 실패 연결에 간선 X로 연결된 노드가 자식 노드의 실패 연결이다.
2. 만약 노드의 실패 연결에 간선 X가 없으면, 바로 그 조상 노드의 간선 X로 연결된 노드가 자식 노드의 실패 연결이다.
3. 이런 식으로 조상 노드를 찾는데, 만일 루트까지 가면 루트가 실패 연결이다.

// 트라이가 주어질 때 각 노드에 대해 실패 연결과 출력 문자열 목록을 계산한다.
void computeFailFunc(TrieNode* root) {
	// 루트에서부터 시작해 한 단계씩 아래로 내려가며 각 노드의 실패 연결을 계산한다.
	queue<TrieNode*> q;
	// 루트의 실패 연결은 자기 자신
	root->fail = root;
	q.push(root);
 
	while(!q.empty()) {
		TrieNode* here = q.front();
		q.pop();
		// here 의 모든 노드에 대해 실패 연결을 계산하고 이들을 큐에 넣는다
		for(int edge = 0; edge < ALPHABETS; ++edge) {
			TrieNode* child = here->children[edge];
			if(!child) continue;
 
			// 1레벨 노드의 실패 연결은 항상 루트
			if(here == root)
				child->fail = root;
			else {
				// 아닌 경우 부모의 실패 연결을 따라가면서 실패 연결을 찾는다
				TrieNode* t = here->fail;
				while(t != root && t->children[edge] == NULL)
					t = t->fail;
				if(t->children[edge]) t = t->children[edge];
				child->fail = t;
			}
			// 출력 문자열 목록: 실패 연결에서 가져온 뒤, 이 위치에서 끝나는 문자열이 있으면 추가한다
			child->output = child->fail->output;
			if(child->terminal != -1)
				child->output.push_back(child->terminal);
			q.push(child);
		}
	}
}

// trie 에 포함된 패턴들을 s 에서 찾는다.
// s 내에서 패턴이 출현할 때마다 (마지막 글자, 패턴 번호) 의 쌍을 저장한다
vector<pair<int,int> > ahoCorasick(const string& s, TrieNode* trie) {
    vector<pair<int,int> > ret;
 
	TrieNode* state = trie;
	// 실제 루프 내는 KMP 와 별로 다를 것이 없다
	for(int i = 0; i < s.size(); i++) {
		int chr = toNumber(s[i]);
		while(state != trie && state->children[chr] == NULL)
			state = state->fail;
		if(state->children[chr]) state = state->children[chr];
		for(int j = 0; j < state->output.size(); ++j)
			ret.push_back(make_pair(i, state->output[j]));
	}
	return ret;
}

설명

• 은행 전산망 해킹을 막는 침입 감지 시스템(IDS)은 네트웍의 모든 트래픽을 감시하면서 특정 문자열을 발견하면 해킹 시도로 인식.
• 서버로 보내지는 데이터에 이 문자열이 포함되어 있으면 않됨.
• 침입 감지 시스템이 인식하는 패턴은 확보됨.
• 루트의 비밀번호는 알파벳 소문자로 구성된 길이 n의 문자열
• 길이 n인 소문자 문자열 중 IDS에 인식되지 않는 문자열의 개수를 구하는 문제.

• 메모리 : 64MB이하.
• 시간 : 1초 이내.

• 입력의 첫 줄은 테스트 케이스 수 C(1⇐C⇐50)
• 각 테스트 케이스의 첫 주에는 만들 문자열의 길이 N(1⇐N⇐ 100)과 IDS가 인식하는 패턴의 수 M(1⇐M⇐100)이 주어진다.
• 그 후 M 줄에 하나씩 길이 10 이하의 알파벳 소문자 문자열로 IDS가 인식하는 패턴이 주어진다.

• 각 테스트 케이스마다 IDS에 인식되지 않는 무자열의 수를 출력하라.
• 문자열의 수가 클 경우 10007로 나눈 나머지를 출혁한다.