Пыщь-пыщь

main.cpp

#include "stdafx.h"

const size_t N_SYMBOLS = 10;
const size_t SYMBOL_SIZE = 5;
const size_t ROW_SIZE = 3;

char raw_symbols[N_SYMBOLS][SYMBOL_SIZE][ROW_SIZE + 1] = {
		{ "111", "101", "101", "101", "111" },
		{ "110", "010", "010", "010", "111" },
		{ "111", "001", "111", "100", "111" },
		{ "111", "001", "111", "001", "111" },
		{ "101", "101", "111", "001", "001" },
		{ "111", "100", "111", "001", "111" },
		{ "111", "100", "111", "101", "111" },
		{ "111", "001", "011", "010", "010" },
		{ "111", "101", "111", "101", "111" },
		{ "111", "101", "111", "001", "111" }
};

string nspaces(size_t n) {
	string buff = "";
	while (n-- > 0) {
		buff += "  ";
	}
	return buff;
}

class TrieSearcher {
public:
	class Node;
	typedef map<char, Node*> LinkMap;
	typedef set<char> ValueSet;
	class SearchProcess {
	public:
		TrieSearcher& searcher;
		Node* pos;
		SearchProcess(TrieSearcher& searcher):searcher(searcher) {
			pos = searcher.root;
		}
		ValueSet step(char c) {
			auto follow = pos->at(c);
			while (!(follow = pos->at(c)) && pos != searcher.root) {
				pos = pos->fail;
			}
			
			if (follow) {
				pos = follow;
			}
				
			return pos->results;
		}
	};

	class Node {
	public:
		size_t index = 0;
		Node *fail;
		LinkMap links;
		ValueSet results;
		static size_t last_index;

		Node() :links(), results() {
			index = last_index++;
		}
		~Node() {
			for each(auto kv in links) {
				if (kv.second) {
					delete kv.second;
				}
			}
		}
		Node* at(char c) {
			LinkMap::iterator i = links.find(c);
			if (i == links.end()) {
				return NULL;
			}
			return i->second;
		}
	};

	Node *root;
	TrieSearcher() {
		root = new Node();
		root->fail = root;
	}
	~TrieSearcher() {
		delete root;
	}
	void add(char* key, char value) {
		Node* p = root;
		while(*key) {
			if (!p->at(*key)) {
				p->links[*key] = new Node();
			}
			p = p->links[*key];
			key++;
		}
		p->results.insert(value);
	}

	void build_fail_links() {
		queue<Node*> Q;
		for each(auto i in root->links) {
			i.second->fail = root;
			Q.push(i.second);
		}

		while (!Q.empty()) {
			Node* r = Q.front();
			Q.pop();
			for each(auto i in r->links) {
				char a = i.first;
				Node* u = i.second;
				Node* v = r->fail;
				Q.push(u);

				Node* fail = NULL;
				while ((fail = v->at(a)) == NULL && v != root) {
					v = v->fail;
				}
				if (fail == NULL) {
					fail = root;
				}
				u->fail = fail;
				u->results.insert(
					v->fail->results.begin(),
					v->fail->results.end()
				);
			}
		}
	}

	SearchProcess* begin_search() {
		return new SearchProcess(*this);
	}
};

size_t TrieSearcher::Node::last_index = 0;

size_t bin_str_to_size_t(char* str) {
	size_t acc = 0;
	while (*str) {
		if (*str == '0') acc *= 2;
		else if (*str == '1') acc = acc * 2 + 1;
		else throw new exception("wtf! str should only contain ones and zeros");

		str++;
	}
	return acc;
}

TrieSearcher* getTrieSearcher() {
	char needles[N_SYMBOLS][SYMBOL_SIZE + 1];
	for (size_t i = 0; i < N_SYMBOLS; i++) {
		auto symbol = raw_symbols[i];
		auto &needle = needles[i];
		for (size_t j = 0; j < SYMBOL_SIZE; j++) {
			needle[j] = '0' + bin_str_to_size_t(raw_symbols[i][j]);
		}
		needle[SYMBOL_SIZE] = '\0';
	}

	auto res = new TrieSearcher();
	for (size_t i = 0; i < N_SYMBOLS; i++) {
		res->add(needles[i], '0' + i);
	}

	res->build_fail_links();
	return res;
}

string foldLine(string str) {
	string res = "";
	size_t acc = 0;
	const size_t mask = (1 << ROW_SIZE) - 1;
	for (size_t i = 0; i < str.size(); i++) {
		char c = str[i];
		if (c == '0') acc *= 2;
		else if (c == '1') acc = acc * 2 + 1;
		else throw new exception("wtf! str should only contain ones and zeros");
		
		if (i < 2) continue;

		acc &= mask;
		res += (acc + '0');
	}
	return res;
}

int _tmain(int argc, _TCHAR* argv[])
{
	if (argc < 2) {
		cout << "Usage: search <filename>" << endl;
		return 0;
	}
	auto inp = ifstream(argv[1]);
	if (!inp.is_open()) {
		cout << "no such file: " << argv[1] << endl;
		return 0;
	}
	TrieSearcher *seeker_factory = getTrieSearcher();

	string buff;
	getline(inp, buff);
	string front = foldLine(buff);
	vector<TrieSearcher::SearchProcess*> seekers;
	for each (auto c in front) {
		seekers.push_back(seeker_factory->begin_search());
	}

	size_t k = 0;

	for (size_t i = 0; !inp.eof(); getline(inp, buff), i++) {
		front = foldLine(buff);
		for (size_t j = 0; j < seekers.size(); j++) {
			auto seeker = seekers[j];
			auto res = seeker->step(front[j]);
			for each(char c in res) {
				cout << k++ << ":\t(" << i << ", " << j << ") \t" << c << endl;
			}
		}
	}

	delete seeker_factory;
	return 0;
}

results.txt

0:	(5, 1) 	0
1:	(5, 5) 	1
2:	(5, 9) 	2
3:	(5, 13) 	3
4:	(5, 17) 	4
5:	(5, 21) 	5
6:	(5, 25) 	6
7:	(5, 29) 	7
8:	(5, 33) 	8
9:	(5, 37) 	9
10:	(5, 42) 	0
11:	(5, 46) 	1
12:	(5, 50) 	2
13:	(5, 54) 	3
14:	(5, 58) 	4
15:	(5, 62) 	5
16:	(5, 66) 	6
17:	(5, 70) 	7
18:	(5, 74) 	8
19:	(5, 78) 	9
20:	(5, 83) 	0
21:	(5, 87) 	1
22:	(5, 91) 	2
23:	(5, 95) 	3
24:	(5, 99) 	4
25:	(5, 103) 	5
26:	(5, 107) 	6
27:	(5, 111) 	7
28:	(5, 115) 	8
29:	(5, 119) 	9
30:	(11, 1) 	0
31:	(11, 5) 	1
32:	(11, 9) 	2
33:	(11, 13) 	3
34:	(11, 17) 	4
35:	(11, 21) 	5
36:	(11, 25) 	6
37:	(11, 29) 	7
38:	(11, 33) 	8
39:	(11, 37) 	9
40:	(11, 42) 	0
41:	(11, 46) 	1
42:	(11, 50) 	2
43:	(11, 54) 	3
44:	(11, 58) 	4
45:	(11, 62) 	5
46:	(11, 66) 	6
47:	(11, 70) 	7
48:	(11, 74) 	8
49:	(11, 78) 	9
50:	(11, 83) 	0
51:	(11, 87) 	1
52:	(11, 91) 	2
53:	(11, 95) 	3
54:	(11, 99) 	4
55:	(11, 103) 	5
56:	(11, 107) 	6
57:	(11, 111) 	7
58:	(11, 115) 	8
59:	(11, 119) 	9
60:	(17, 1) 	0
61:	(17, 5) 	1
62:	(17, 9) 	2
63:	(17, 13) 	3
64:	(17, 17) 	4
65:	(17, 21) 	5
66:	(17, 25) 	6
67:	(17, 29) 	7
68:	(17, 33) 	8
69:	(17, 37) 	9
70:	(17, 42) 	0
71:	(17, 46) 	1
72:	(17, 50) 	2
73:	(17, 54) 	3
74:	(17, 58) 	4
75:	(17, 62) 	5
76:	(17, 66) 	6
77:	(17, 70) 	7
78:	(17, 74) 	8
79:	(17, 78) 	9
80:	(17, 83) 	0
81:	(17, 87) 	1
82:	(17, 91) 	2
83:	(17, 95) 	3
84:	(17, 99) 	4
85:	(17, 103) 	5
86:	(17, 107) 	6
87:	(17, 111) 	7
88:	(17, 115) 	8
89:	(17, 119) 	9
90:	(23, 1) 	0
91:	(23, 5) 	1
92:	(23, 9) 	2
93:	(23, 13) 	3
94:	(23, 17) 	4
95:	(23, 21) 	5
96:	(23, 25) 	6
97:	(23, 29) 	7
98:	(23, 33) 	8
99:	(23, 37) 	9
100:	(23, 42) 	0
101:	(23, 46) 	1
102:	(23, 50) 	2
103:	(23, 54) 	3
104:	(23, 58) 	4
105:	(23, 62) 	5
106:	(23, 66) 	6
107:	(23, 70) 	7
108:	(23, 74) 	8
109:	(23, 78) 	9
110:	(23, 83) 	0
111:	(23, 87) 	1
112:	(23, 91) 	2
113:	(23, 95) 	3
114:	(23, 99) 	4
115:	(23, 103) 	5
116:	(23, 107) 	6
117:	(23, 111) 	7
118:	(23, 115) 	8
119:	(23, 119) 	9
120:	(29, 1) 	0
121:	(29, 5) 	1
122:	(29, 9) 	2
123:	(29, 13) 	3
124:	(29, 17) 	4
125:	(29, 21) 	5
126:	(29, 25) 	6
127:	(29, 29) 	7
128:	(29, 33) 	8
129:	(29, 37) 	9
130:	(29, 42) 	0
131:	(29, 46) 	1
132:	(29, 50) 	2
133:	(29, 54) 	3
134:	(29, 58) 	4
135:	(29, 62) 	5
136:	(29, 66) 	6
137:	(29, 70) 	7
138:	(29, 74) 	8
139:	(29, 78) 	9
140:	(29, 83) 	0
141:	(29, 87) 	1
142:	(29, 91) 	2
143:	(29, 95) 	3
144:	(29, 99) 	4
145:	(29, 103) 	5
146:	(29, 107) 	6
147:	(29, 111) 	7
148:	(29, 115) 	8
149:	(29, 119) 	9
150:	(35, 1) 	0
151:	(35, 5) 	1
152:	(35, 9) 	2
153:	(35, 13) 	3
154:	(35, 17) 	4
155:	(35, 21) 	5
156:	(35, 25) 	6
157:	(35, 29) 	7
158:	(35, 33) 	8
159:	(35, 37) 	9
160:	(35, 42) 	0
161:	(35, 46) 	1
162:	(35, 50) 	2
163:	(35, 54) 	3
164:	(35, 58) 	4
165:	(35, 62) 	5
166:	(35, 66) 	6
167:	(35, 70) 	7
168:	(35, 74) 	8
169:	(35, 78) 	9
170:	(35, 83) 	0
171:	(35, 87) 	1
172:	(35, 91) 	2
173:	(35, 95) 	3
174:	(35, 99) 	4
175:	(35, 103) 	5
176:	(35, 107) 	6
177:	(35, 111) 	7
178:	(35, 115) 	8
179:	(35, 119) 	9
180:	(41, 1) 	0
181:	(41, 5) 	1
182:	(41, 9) 	2
183:	(41, 13) 	3
184:	(41, 17) 	4
185:	(41, 21) 	5
186:	(41, 25) 	6
187:	(41, 29) 	7
188:	(41, 33) 	8
189:	(41, 37) 	9
190:	(41, 42) 	0
191:	(41, 46) 	1
192:	(41, 50) 	2
193:	(41, 54) 	3
194:	(41, 58) 	4
195:	(41, 62) 	5
196:	(41, 66) 	6
197:	(41, 70) 	7
198:	(41, 74) 	8
199:	(41, 78) 	9
200:	(41, 83) 	0
201:	(41, 87) 	1
202:	(41, 91) 	2
203:	(41, 95) 	3
204:	(41, 99) 	4
205:	(41, 103) 	5
206:	(41, 107) 	6
207:	(41, 111) 	7
208:	(41, 115) 	8
209:	(41, 119) 	9
210:	(47, 1) 	0
211:	(47, 5) 	1
212:	(47, 9) 	2
213:	(47, 13) 	3
214:	(47, 17) 	4
215:	(47, 21) 	5
216:	(47, 25) 	6
217:	(47, 29) 	7
218:	(47, 33) 	8
219:	(47, 37) 	9
220:	(47, 42) 	0
221:	(47, 46) 	1
222:	(47, 50) 	2
223:	(47, 54) 	3
224:	(47, 58) 	4
225:	(47, 62) 	5
226:	(47, 66) 	6
227:	(47, 70) 	7
228:	(47, 74) 	8
229:	(47, 78) 	9
230:	(47, 83) 	0
231:	(47, 87) 	1
232:	(47, 91) 	2
233:	(47, 95) 	3
234:	(47, 99) 	4
235:	(47, 103) 	5
236:	(47, 107) 	6
237:	(47, 111) 	7
238:	(47, 115) 	8
239:	(47, 119) 	9
240:	(53, 1) 	0
241:	(53, 5) 	1
242:	(53, 9) 	2
243:	(53, 13) 	3
244:	(53, 17) 	4
245:	(53, 21) 	5
246:	(53, 25) 	6
247:	(53, 29) 	7
248:	(53, 33) 	8
249:	(53, 37) 	9
250:	(53, 42) 	0
251:	(53, 46) 	1
252:	(53, 50) 	2
253:	(53, 54) 	3
254:	(53, 58) 	4
255:	(53, 62) 	5
256:	(53, 66) 	6
257:	(53, 70) 	7
258:	(53, 74) 	8
259:	(53, 78) 	9
260:	(53, 83) 	0
261:	(53, 87) 	1
262:	(53, 91) 	2
263:	(53, 95) 	3
264:	(53, 99) 	4
265:	(53, 103) 	5
266:	(53, 107) 	6
267:	(53, 111) 	7
268:	(53, 115) 	8
269:	(53, 119) 	9
270:	(59, 1) 	0
271:	(59, 5) 	1
272:	(59, 9) 	2
273:	(59, 13) 	3
274:	(59, 17) 	4
275:	(59, 21) 	5
276:	(59, 25) 	6
277:	(59, 29) 	7
278:	(59, 33) 	8
279:	(59, 37) 	9
280:	(59, 42) 	0
281:	(59, 46) 	1
282:	(59, 50) 	2
283:	(59, 54) 	3
284:	(59, 58) 	4
285:	(59, 62) 	5
286:	(59, 66) 	6
287:	(59, 70) 	7
288:	(59, 74) 	8
289:	(59, 78) 	9
290:	(59, 83) 	0
291:	(59, 87) 	1
292:	(59, 91) 	2
293:	(59, 95) 	3
294:	(59, 99) 	4
295:	(59, 103) 	5
296:	(59, 107) 	6
297:	(59, 111) 	7
298:	(59, 115) 	8
299:	(59, 119) 	9

stdafx.h

#pragma once

#include "targetver.h"

#include <stdio.h>
#include <tchar.h>

#include <iostream>
#include <fstream>
#include <string>
#include <map>
#include <set>
#include <queue>
#include <exception>

using namespace std;