#include <iostream>
#include <map>
#include <set>
#include<algorithm>
#include <iterator>
using namespace std;
int main() {
// your code goes here
/*string data[5][5] = { {"A","B","FG","C","D"} ,
{"B","G","D"},
{"B","F","G","AB"},
{"F","AB","C","D"},
{"A","BC","G","F","DE"}
};
int min_support = 2;
set<char> unique_events; // sets hold unique values
map<char, int> unique_support; // map each unique value to it's support
for (int row = 0; row < 5; row++) {
for (int col = 0; col < 5; col++) {
for (int s = 0; s < data[row][col].length(); s++) {
// looping over the dataset to insert unique events into the set
unique_events.insert(data[row][col][s]);
}
}
}
set<char> ::iterator it;
map<char, int> ::iterator t;
map<char, int> ::iterator loop;
// iterating over each event in the set comparing it to the row in the dataset
// (whether it appeared n the row or not) if yes, break from that row incrementing it's support
// in the map
for (it = unique_events.begin(); it != unique_events.end(); it++) {
for (int row = 0; row < 5; row++) {
bool found = false;
for (int col = 0; col < 5; col++) {
for (int s = 0; s < data[row][col].length(); s++) {
if (*it == data[row][col][s]) {
//searching for the event in the map exists or not
t = unique_support.find(data[row][col][s]);
if (t != unique_support.end())
t->second++;
else
unique_support.insert(pair<char,int>(data[row][col][s],1));
found = true;
}
if (found)
break;
}
if (found)
break;
}
}
}
/// pruning support
for (t = unique_support.begin(); t != unique_support.end(); ) {
if (t->second < min_support) {
loop = t;
unique_events.erase(t->first);
t++;
unique_support.erase(loop); // if support < min_support , delete from the map
}
else
t++;
}
////// CANDIDATE GENERATION OF SIZE 2
set<string> candidatesSize2;
//string candidatesSize2[100];
set<char> ::iterator item1;
set<char> ::iterator item2;
int i = 0;
for (item1 = unique_events.begin(); item1 != unique_events.end(); item1++) {
for (item2 = unique_events.begin(); item2 != unique_events.end(); item2++) {
string a, b;
a.append(1, *item1);
b.append(1, *item2);
string h = a + ' '+ b;
candidatesSize2.insert(h);
}
}
for (item1 = unique_events.begin(); item1 != unique_events.end(); item1++) {
it = item1;
for (item2 = ++it; item2 != unique_events.end(); item2++) {
//cout << *it << endl;
//cout << *item1 << " " << *item2 << endl;
string a, b;
a.append(1, *item1);
b.append(1, *item2);
string h = a + b;
candidatesSize2.insert(h);
}
}
*/
set<string> ::iterator item11;
set<string> ::iterator item22;
set<string> candidatesSize3;
set<string> candidatesSize2;
candidatesSize2.insert("b b");
candidatesSize2.insert("a b");
candidatesSize2.insert("b c");
candidatesSize2.insert("c b");
candidatesSize2.insert("bd");
candidatesSize2.insert("d b");
candidatesSize2.insert("b e");
candidatesSize2.insert("d c");
candidatesSize2.insert("ce");
for (item11 = candidatesSize2.begin(); item11 != candidatesSize2.end(); item11++) {
for (item22 = candidatesSize2.begin(); item22 != candidatesSize2.end(); item22++) {
string a, b, c;
string i1=*item11,i2=*item22;
if (i1.size() == 3&& i2.size() == 3)
{
if (i1[2] == i2[0])
{
a.append(1, i1[0]);
b.append(1, i2[0]);
c.append(1, i2[2]);
string h = a + ' ' + b + ' ' + c;
candidatesSize3.insert(h);
}
}
else if (i1.size() == 3&& i2.size() == 2)
{
if (i1[2] == i2[0])
{
a.append(1, i1[0]);
b.append(1, i2[0]);
c.append(1, i2[1]);
string h = a + ' ' + b + c;
candidatesSize3.insert(h);
}
}
else if (i1.size() == 2&& i2.size() == 3)
{
if (i1[1] == i2[0])
{
a.append(1, i1[0]);
b.append(1, i2[0]);
c.append(1, i2[2]);
string h = a + b + ' ' + c;
candidatesSize3.insert(h);
}
}
else
{
if (i1[1] == i2[0])
{
a.append(1, i1[0]);
b.append(1, i2[0]);
c.append(1, i2[1]);
string h = a + b + c;
candidatesSize3.insert(h);
}
}
}
}
set<string> ::iterator sz;
for (sz = candidatesSize3.begin(); sz != candidatesSize3.end(); sz++) {
cout << *sz << endl;
}
return 0;
}
I2luY2x1ZGUgPGlvc3RyZWFtPgojaW5jbHVkZSA8bWFwPgojaW5jbHVkZSA8c2V0PgojaW5jbHVkZTxhbGdvcml0aG0+CiNpbmNsdWRlIDxpdGVyYXRvcj4KdXNpbmcgbmFtZXNwYWNlIHN0ZDsKCmludCBtYWluKCkgewoJLy8geW91ciBjb2RlIGdvZXMgaGVyZQoJCgkvKnN0cmluZyBkYXRhWzVdWzVdID0geyAgIHsiQSIsIkIiLCJGRyIsIkMiLCJEIn0gLAoJCQkJCQkJeyJCIiwiRyIsIkQifSwKCQkJCQkJCXsiQiIsIkYiLCJHIiwiQUIifSwKCQkJCQkJCXsiRiIsIkFCIiwiQyIsIkQifSwKCQkJCQkJCXsiQSIsIkJDIiwiRyIsIkYiLCJERSJ9Cgl9OwoJaW50IG1pbl9zdXBwb3J0ID0gMjsKCXNldDxjaGFyPiB1bmlxdWVfZXZlbnRzOyAvLyBzZXRzIGhvbGQgdW5pcXVlIHZhbHVlcwoJbWFwPGNoYXIsIGludD4gdW5pcXVlX3N1cHBvcnQ7IC8vIG1hcCBlYWNoIHVuaXF1ZSB2YWx1ZSB0byBpdCdzIHN1cHBvcnQKCQoJZm9yIChpbnQgcm93ID0gMDsgcm93IDwgNTsgcm93KyspIHsKCQlmb3IgKGludCBjb2wgPSAwOyBjb2wgPCA1OyBjb2wrKykgewoJCQlmb3IgKGludCBzID0gMDsgcyA8IGRhdGFbcm93XVtjb2xdLmxlbmd0aCgpOyBzKyspIHsKCQkJCS8vIGxvb3Bpbmcgb3ZlciB0aGUgZGF0YXNldCB0byBpbnNlcnQgdW5pcXVlIGV2ZW50cyBpbnRvIHRoZSBzZXQKCQkJCXVuaXF1ZV9ldmVudHMuaW5zZXJ0KGRhdGFbcm93XVtjb2xdW3NdKTsKCQkJfQoJCX0KCX0KCglzZXQ8Y2hhcj4gOjppdGVyYXRvciBpdDsKCW1hcDxjaGFyLCBpbnQ+IDo6aXRlcmF0b3IgdDsKCW1hcDxjaGFyLCBpbnQ+IDo6aXRlcmF0b3IgbG9vcDsKCQoJLy8gaXRlcmF0aW5nIG92ZXIgZWFjaCBldmVudCBpbiB0aGUgc2V0IGNvbXBhcmluZyBpdCB0byB0aGUgcm93IGluIHRoZSBkYXRhc2V0IAoJLy8gKHdoZXRoZXIgaXQgYXBwZWFyZWQgbiB0aGUgcm93IG9yIG5vdCkgaWYgeWVzLCBicmVhayBmcm9tIHRoYXQgcm93IGluY3JlbWVudGluZyBpdCdzIHN1cHBvcnQgCgkvLyBpbiB0aGUgbWFwCglmb3IgKGl0ID0gdW5pcXVlX2V2ZW50cy5iZWdpbigpOyBpdCAhPSB1bmlxdWVfZXZlbnRzLmVuZCgpOyBpdCsrKSB7CgkJZm9yIChpbnQgcm93ID0gMDsgcm93IDwgNTsgcm93KyspIHsKCgkJCWJvb2wgZm91bmQgPSBmYWxzZTsKCgkJCWZvciAoaW50IGNvbCA9IDA7IGNvbCA8IDU7IGNvbCsrKSB7CgkJCQlmb3IgKGludCBzID0gMDsgcyA8IGRhdGFbcm93XVtjb2xdLmxlbmd0aCgpOyBzKyspIHsKCgkJCQkJaWYgKCppdCA9PSBkYXRhW3Jvd11bY29sXVtzXSkgewoJCQkJCQkvL3NlYXJjaGluZyBmb3IgdGhlIGV2ZW50IGluIHRoZSBtYXAgZXhpc3RzIG9yIG5vdAoJCQkJCQl0ID0gdW5pcXVlX3N1cHBvcnQuZmluZChkYXRhW3Jvd11bY29sXVtzXSk7CgkJCQkJCWlmICh0ICE9IHVuaXF1ZV9zdXBwb3J0LmVuZCgpKQoJCQkJCQkJdC0+c2Vjb25kKys7CgkJCQkJCWVsc2UJCQkJCQoJCQkJCQkJdW5pcXVlX3N1cHBvcnQuaW5zZXJ0KHBhaXI8Y2hhcixpbnQ+KGRhdGFbcm93XVtjb2xdW3NdLDEpKTsKCQkJCQkJZm91bmQgPSB0cnVlOwoJCQkJCX0KCQkJCQlpZiAoZm91bmQpCgkJCQkJCWJyZWFrOwoJCQkJfQoJCQkJaWYgKGZvdW5kKQoJCQkJCWJyZWFrOwoJCQl9CgkJCQoJCX0KCX0KCS8vLyBwcnVuaW5nIHN1cHBvcnQgCglmb3IgKHQgPSB1bmlxdWVfc3VwcG9ydC5iZWdpbigpOyB0ICE9IHVuaXF1ZV9zdXBwb3J0LmVuZCgpOyApIHsKCQlpZiAodC0+c2Vjb25kIDwgbWluX3N1cHBvcnQpIHsKCQkJbG9vcCA9IHQ7CgkJCXVuaXF1ZV9ldmVudHMuZXJhc2UodC0+Zmlyc3QpOwoJCQl0Kys7CgkJCXVuaXF1ZV9zdXBwb3J0LmVyYXNlKGxvb3ApOyAvLyBpZiBzdXBwb3J0IDwgbWluX3N1cHBvcnQgLCBkZWxldGUgZnJvbSB0aGUgbWFwCgkJCQoJCX0KCQllbHNlCgkJCXQrKzsKCQkJCgl9CgkKCQoJLy8vLy8vIENBTkRJREFURSBHRU5FUkFUSU9OIE9GIFNJWkUgMgoJc2V0PHN0cmluZz4gY2FuZGlkYXRlc1NpemUyOwoJLy9zdHJpbmcgY2FuZGlkYXRlc1NpemUyWzEwMF07CglzZXQ8Y2hhcj4gOjppdGVyYXRvciBpdGVtMTsKCXNldDxjaGFyPiA6Oml0ZXJhdG9yIGl0ZW0yOwoJaW50IGkgPSAwOwoJZm9yIChpdGVtMSA9IHVuaXF1ZV9ldmVudHMuYmVnaW4oKTsgaXRlbTEgIT0gdW5pcXVlX2V2ZW50cy5lbmQoKTsgaXRlbTErKykgewoJCWZvciAoaXRlbTIgPSB1bmlxdWVfZXZlbnRzLmJlZ2luKCk7IGl0ZW0yICE9IHVuaXF1ZV9ldmVudHMuZW5kKCk7IGl0ZW0yKyspIHsKCQkJc3RyaW5nIGEsIGI7CgkJCWEuYXBwZW5kKDEsICppdGVtMSk7CgkJCWIuYXBwZW5kKDEsICppdGVtMik7CgkJCXN0cmluZyBoID0gYSArICcgJysgYjsKCQkJCgkJCWNhbmRpZGF0ZXNTaXplMi5pbnNlcnQoaCk7CQkJCgkJfQoJfQoKCWZvciAoaXRlbTEgPSB1bmlxdWVfZXZlbnRzLmJlZ2luKCk7IGl0ZW0xICE9IHVuaXF1ZV9ldmVudHMuZW5kKCk7IGl0ZW0xKyspIHsKCQlpdCA9IGl0ZW0xOwoJCWZvciAoaXRlbTIgPSArK2l0OyBpdGVtMiAhPSB1bmlxdWVfZXZlbnRzLmVuZCgpOyBpdGVtMisrKSB7CgkJCS8vY291dCA8PCAqaXQgPDwgZW5kbDsKCQkJLy9jb3V0IDw8ICppdGVtMSA8PCAiICIgPDwgKml0ZW0yIDw8IGVuZGw7CgkJCXN0cmluZyBhLCBiOwoJCQlhLmFwcGVuZCgxLCAqaXRlbTEpOwoJCQliLmFwcGVuZCgxLCAqaXRlbTIpOwoJCQlzdHJpbmcgaCA9IGEgKyBiOwoKCQkJY2FuZGlkYXRlc1NpemUyLmluc2VydChoKTsKCQl9Cgl9CgkKCSovCgkJc2V0PHN0cmluZz4gOjppdGVyYXRvciBpdGVtMTE7CgkJc2V0PHN0cmluZz4gOjppdGVyYXRvciBpdGVtMjI7CglzZXQ8c3RyaW5nPiBjYW5kaWRhdGVzU2l6ZTM7CgoJc2V0PHN0cmluZz4gY2FuZGlkYXRlc1NpemUyOwoJCQkJY2FuZGlkYXRlc1NpemUyLmluc2VydCgiYiBiIik7CgkJCQljYW5kaWRhdGVzU2l6ZTIuaW5zZXJ0KCJhIGIiKTsKCQkJCWNhbmRpZGF0ZXNTaXplMi5pbnNlcnQoImIgYyIpOwoJCQkJY2FuZGlkYXRlc1NpemUyLmluc2VydCgiYyBiIik7CgkJCQljYW5kaWRhdGVzU2l6ZTIuaW5zZXJ0KCJiZCIpOwoJCQkJY2FuZGlkYXRlc1NpemUyLmluc2VydCgiZCBiIik7CgkJCQljYW5kaWRhdGVzU2l6ZTIuaW5zZXJ0KCJiIGUiKTsKCQkJCWNhbmRpZGF0ZXNTaXplMi5pbnNlcnQoImQgYyIpOwogICAgICAgICAgICAgICAgY2FuZGlkYXRlc1NpemUyLmluc2VydCgiY2UiKTsKCgkJCQkKCgkKCQoJZm9yIChpdGVtMTEgPSBjYW5kaWRhdGVzU2l6ZTIuYmVnaW4oKTsgaXRlbTExICE9IGNhbmRpZGF0ZXNTaXplMi5lbmQoKTsgaXRlbTExKyspIHsKCQlmb3IgKGl0ZW0yMiA9IGNhbmRpZGF0ZXNTaXplMi5iZWdpbigpOyBpdGVtMjIgIT0gY2FuZGlkYXRlc1NpemUyLmVuZCgpOyBpdGVtMjIrKykgewoJCQlzdHJpbmcgYSwgYiwgYzsKCQkJc3RyaW5nIGkxPSppdGVtMTEsaTI9Kml0ZW0yMjsKCQkJaWYgKGkxLnNpemUoKSA9PSAzJiYgaTIuc2l6ZSgpID09IDMpCgkJCXsKCQkJCWlmIChpMVsyXSA9PSBpMlswXSkKCQkJCXsKCQkJCQlhLmFwcGVuZCgxLCBpMVswXSk7CgkJCQkJYi5hcHBlbmQoMSwgaTJbMF0pOwoJCQkJCWMuYXBwZW5kKDEsIGkyWzJdKTsKCQkJCQlzdHJpbmcgaCA9IGEgKyAnICcgKyBiICsgJyAnICsgYzsKCQkJCQljYW5kaWRhdGVzU2l6ZTMuaW5zZXJ0KGgpOwoKCQkJCX0KCQkJfQoJCQllbHNlIGlmIChpMS5zaXplKCkgPT0gMyYmIGkyLnNpemUoKSA9PSAyKQoJCQl7CgkJCQlpZiAoaTFbMl0gPT0gaTJbMF0pCgkJCQl7CgkJCQkJYS5hcHBlbmQoMSwgaTFbMF0pOwoJCQkJCWIuYXBwZW5kKDEsIGkyWzBdKTsKCQkJCQljLmFwcGVuZCgxLCBpMlsxXSk7CgkJCQkJc3RyaW5nIGggPSBhICsgJyAnICsgYiAgKyBjOwoJCQkJCWNhbmRpZGF0ZXNTaXplMy5pbnNlcnQoaCk7CgoJCQkJfQoJCQl9CgkJCWVsc2UgaWYgKGkxLnNpemUoKSA9PSAyJiYgaTIuc2l6ZSgpID09IDMpCgkJCXsKCQkJCWlmIChpMVsxXSA9PSBpMlswXSkKCQkJCXsKCQkJCQlhLmFwcGVuZCgxLCBpMVswXSk7CgkJCQkJYi5hcHBlbmQoMSwgaTJbMF0pOwoJCQkJCWMuYXBwZW5kKDEsIGkyWzJdKTsKCQkJCQlzdHJpbmcgaCA9IGEgKyAgYiArICcgJyArIGM7CgkJCQkJY2FuZGlkYXRlc1NpemUzLmluc2VydChoKTsKCgkJCQl9CgkJCX0KCQkJZWxzZQoJCQl7CgkJCQlpZiAoaTFbMV0gPT0gaTJbMF0pCgkJCQl7CgkJCQkJYS5hcHBlbmQoMSwgaTFbMF0pOwoJCQkJCWIuYXBwZW5kKDEsIGkyWzBdKTsKCQkJCQljLmFwcGVuZCgxLCBpMlsxXSk7CgkJCQkJc3RyaW5nIGggPSBhICsgIGIgICsgYzsKCQkJCQljYW5kaWRhdGVzU2l6ZTMuaW5zZXJ0KGgpOwoKCQkJCX0KCQkJfQoKCQl9Cgl9CgoJc2V0PHN0cmluZz4gOjppdGVyYXRvciBzejsKCWZvciAoc3ogPSBjYW5kaWRhdGVzU2l6ZTMuYmVnaW4oKTsgc3ogIT0gY2FuZGlkYXRlc1NpemUzLmVuZCgpOyBzeisrKSB7CgkJY291dCA8PCAqc3ogPDwgZW5kbDsKCX0KCgkKCXJldHVybiAwOwp9