#include #include #include using namespace std; int equals[1024][1024]; int table[1025][1025]; int input(char s[1025]) { int c, len = 0; while (1) { c = getchar(); if (feof(stdin)) { return len; } if ('a' <= c && c <= 'z') { s[len] = c - 0x20; len++; } else if ('A' <= c && c <= 'Z') { s[len] = c; len++; } else if (c == '\n') { s[len] = '\0'; break; } } return len; } void make_equals(char s[1025], int len) { int i, j; for (i = 0; i < len; i++) { for (j = 0; j < len; j++) { if (s[i] == s[j]) { equals[i][j] = 1; } else { equals[i][j] = 0; } } } } /* Dynamic Programming table[leftmost][width] = table[leftmost+1][width-2] && equals[leftmost][leftmost+width-1] */ void make_table(char s[1025], int len) { int leftmost, width; for (width = 1; width <= len; width++) { for (leftmost = 0; leftmost < (len - width + 1); leftmost++) { if (width == 1) { table[leftmost][width] = 1; } else if (width == 2) { if (s[leftmost] == s[leftmost+1]) { table[leftmost][width] = 1; } else { table[leftmost][width] = 0; } } else { table[leftmost][width] = table[leftmost+1][width-2] && equals[leftmost][leftmost+width-1]; } } } } void println_sets(set longests[1025]) { bool first = true; set all; for (int i = 0; i < 1025; i++) { for (set::iterator p = longests[i].begin(); p != longests[i].end(); p++) { all.insert(*p); } } for (set::iterator p = all.begin(); p != all.end(); p++) { if (first) { first = false; } else { printf(" "); } printf("%s", p->c_str()); } printf("\n"); } void uniq_print(string &str, int len) { int leftmost, width; set centors[1025], longests[1025]; for (width = 3; width <= len; width++) { for (leftmost = 0; leftmost < (len - width + 1); leftmost++) { if (table[leftmost][width]) { string substr = str.substr(leftmost, width); /* Clearly, "substr" is the same as the centor of the other string */ if (leftmost > 0 && leftmost+width < len && table[leftmost-1][width+2]) { centors[width].insert(substr); longests[width].erase(substr); } else { if (centors[width].find(substr) == centors[width].end()) { longests[width].insert(substr); } } } } } println_sets(longests); } int main() { char s[1025]; int len; while (1) { len = input(s); if (feof(stdin)) { break; } make_equals(s, len); make_table(s, len); string str = string(s); uniq_print(str, len); } return 0; }