paizaラーニングレベルアップ問題集の「文字列収集」をやってみた

paiza×Qiita記事投稿キャンペーンということで、paizaラーニングレベルアップ問題集の[文字列収集](https://paiza.jp/works/mondai/real_event/word_collection)をやってみました。
- - -
入力の後半でクエリ文字列が来てから市場に出回っている$N$個の文字列を精査していては、時間がかかりすぎてしまいます。予め、このクエリ文字列が来たら必要金額はいくら、ということを計算しておきましょう。クエリ文字列と必要金額は、連想配列に格納しておきます。（下の表の、太字の入力に対して、細字の文字列と数値を格納。同じ文字列（キー）が来たら数値を足し合わせる）
| bcac | 3 |
|:-:|:-:|
| b | 3 |
| bc | 3 |
| bca | 3 |
| bcac | 3 |
```cpp
#include <iostream>
#include <map>
#include <utility>
using namespace std;

int main() {
	int n, m;
	cin >> n >> m;
	map<string, int> dict;
	for (int i = 0; i < n; i++) {
		string s;
		int p;
		cin >> s >> p;
		for (int j = 1; j <= s.size(); j++) {
			dict[s.substr(0, j)] += p; //s.substr(0,j)がdictに登録されていない場合はdict[s.substr(0,j)]に0+pが格納される。
		}
	}
	for (int i = 0; i < m; i++) {
		string q;
		cin >> q;
		cout << dict[q] << endl;
	}
	return 0;
}
```
C++の`map`は、連想配列に登録されていないキーに対する値を求めようとしたとき、デフォルト値が返されます（値が`int`型の場合は`0`）。Pythonの`defaultdict`も同様です。しかし、多くの言語では、連想配列に登録されていないキーに対する値を求めようとするとエラーになりますので、既にキーが登録されている/されていないでチェック＆分岐処理が必要になります。
- - -
以上で終わりなのですが、[トライ木](https://ja.wikipedia.org/wiki/%E3%83%88%E3%83%A9%E3%82%A4_(%E3%83%87%E3%83%BC%E3%82%BF%E6%A7%8B%E9%80%A0))というものを使って実装してみましょう。よく分からないという方は、リンク先やタグ遷移先を参照してください。
[トライ木メニュー](https://paiza.jp/works/mondai/trie_problems/problem_index)を参考にして[トライ木](https://paiza.jp/works/mondai/aho_corasick_problem/aho_corasick__matching_step2)を実装してみます。今回は、この問題を解けるように改変しています。
```c
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct Node {
	int value; //合計必要金額
	struct Node *child[26];
} Node;

typedef struct Trie {
	Node *root;
} Trie;

void insert(Trie *trie, const char *key, int value) {
	Node *node = trie->root;
	for (const char *c = key; *c; c++) {
		int ch = (int) (*c - 'a');
		if (!node->child[ch]) {
			if (!(node->child[ch] = (Node*) malloc(sizeof(Node)))) {
				abort();
			}
			memset(node->child[ch], 0, sizeof(Node));
		}
		node->child[ch]->value += value;
		node = node->child[ch];
	}
}

int search(const Trie *trie, const char *key) {
	Node *node = trie->root;
	for (const char *c = key; *c; c++) {
		int ch = (int) (*c - 'a');
		if (!node->child[ch]) {
			return 0;
		}
		node = node->child[ch];
	}
	return node->value;
}

void _clear(Node *node) {
	for (char c = 'a'; c <= 'z'; c++) {
		if (node->child[c - 'a']) {
			_clear(node->child[c - 'a']);
		}
	}
	free(node);
}

void clear(Trie *trie) {
	_clear(trie->root);
	trie->root = NULL;
}
```
- - -
上のトライ木を用いて、問題を解いていきます。
```c
int main() {
	int n, m;
	scanf("%d %d", &n, &m);

	Trie trie;
	trie.root = (Node*) malloc(sizeof(Node));
	memset(trie.root, 0, sizeof(Node));
	for (int i = 0; i < n; i++) {
		char s[101];
		int p;
		scanf("%s %d", s, &p);
		insert(&trie, s, p);
	}
	for (int i = 0; i < m; i++) {
		char q[101];
		scanf("%s", q);
		printf("%d\n", search(&trie, q));
	}
	clear(&trie);
	return 0;
}
```
- - -
問題文の入力例1では、まず、以下のようにトライ木に格納されます。
`bcac 3`
```mermaid
graph LR
0(( ))==b==>1[3]==c==>2[3]==a==>3[3]==c==>4[3]
```
`abcd 14`
```mermaid
graph LR
0(( ))==a==>5[14]==b==>6[14]==c==>7[14]==d==>8[14]
0--b-->1[3]--c-->2[3]--a-->3[3]--c-->4[3]
```
`abccjg 92`
```mermaid
graph LR
0(( ))==a==>5[106]==b==>6[106]==c==>7[106]--d-->8[14]
7==c==>9[92]==j==>10[92]==g==>11[92]
0--b-->1[3]--c-->2[3]--a-->3[3]--c-->4[3]
```
`bcaddgie 2`
```mermaid
graph LR
0(( ))--a-->5[106]--b-->6[106]--c-->7[106]--d-->8[14]
7--c-->9[92]--j-->10[92]--g-->11[92]
0==b==>1[5]==c==>2[5]==a==>3[5]--c-->4[3]
3==d==>12[2]==d==>13[2]==g==>14[2]==i==>15[2]==e==>16[2]
```
`abcd 6`
```mermaid
graph LR
0(( ))==a==>5[112]==b==>6[112]==c==>7[112]==d==>8[20]
7--c-->9[92]--j-->10[92]--g-->11[92]
0--b-->1[5]--c-->2[5]--a-->3[5]--c-->4[3]
3--d-->12[2]--d-->13[2]--g-->14[2]--i-->15[2]--e-->16[2]
```
`cd 200`
```mermaid
graph LR
0(( ))--a-->5[112]--b-->6[112]--c-->7[112]--d-->8[20]
7--c-->9[92]--j-->10[92]--g-->11[92]
0--b-->1[5]--c-->2[5]--a-->3[5]--c-->4[3]
3--d-->12[2]--d-->13[2]--g-->14[2]--i-->15[2]--e-->16[2]
0==c==>17[200]==b==>18[200]
```
- - -
そして、以下のように値を取り出していきます。丸ノードの値が答えです。
`b`
```mermaid
graph LR
0(( ))--a-->5[112]--b-->6[112]--c-->7[112]--d-->8[20]
7--c-->9[92]--j-->10[92]--g-->11[92]
0==b==>1([5])--c-->2[5]--a-->3[5]--c-->4[3]
3--d-->12[2]--d-->13[2]--g-->14[2]--i-->15[2]--e-->16[2]
0--c-->17[200]--b-->18[200]
```
- - -
`a`
```mermaid
graph LR
0(( ))==a==>5([112])--b-->6[112]--c-->7[112]--d-->8[20]
7--c-->9[92]--j-->10[92]--g-->11[92]
0--b-->1[5]--c-->2[5]--a-->3[5]--c-->4[3]
3--d-->12[2]--d-->13[2]--g-->14[2]--i-->15[2]--e-->16[2]
0--c-->17[200]--b-->18[200]
```
- - -
`abcd`
```mermaid
graph LR
0(( ))==a==>5[112]==b==>6[112]==c==>7[112]==d==>8([20])
7--c-->9[92]--j-->10[92]--g-->11[92]
0--b-->1[5]--c-->2[5]--a-->3[5]--c-->4[3]
3--d-->12[2]--d-->13[2]--g-->14[2]--i-->15[2]--e-->16[2]
0--c-->17[200]--b-->18[200]
```
- - -
`gagioheo`
```mermaid
graph LR
0(( ))--a-->5[112]--b-->6[112]--c-->7[112]--d-->8[20]
7--c-->9[92]--j-->10[92]--g-->11[92]
0--b-->1[5]--c-->2[5]--a-->3[5]--c-->4[3]
3--d-->12[2]--d-->13[2]--g-->14[2]--i-->15[2]--e-->16[2]
0--c-->17[200]--b-->18[200]
0-.g.->19(( ))
```
`gagioheo`で始まる単語は格納されていませんので、`0`が答えです。
- - -
`cb`
```mermaid
graph LR
0(( ))--a-->5[112]--b-->6[112]--c-->7[112]--d-->8[20]
7--c-->9[92]--j-->10[92]--g-->11[92]
0--b-->1[5]--c-->2[5]--a-->3[5]--c-->4[3]
3--d-->12[2]--d-->13[2]--g-->14[2]--i-->15[2]--e-->16[2]
0==c==>17[200]==b==>18([200])
```