Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- #include <map>
- #include <cstring>
- using namespace std;
- typedef long long ll;
- const int maxn = 205;
- const int alphabet_size = 26;
- map<int, int> at_trie_is_end_of_word;
- int trie[maxn][alphabet_size];
- ll dp[28][1 << 9][maxn];
- int o, n;
- ll rec(int at, int visited, int at_trie) {
- if(at == o and __builtin_popcount(visited) == n) {
- return 1;
- }
- if(at >= o) {
- return 0;
- }
- if(dp[at][visited][at_trie] != -1) {
- return dp[at][visited][at_trie];
- }
- ll res = 0;
- for(char c = 'a'; c <= 'z'; c++) {
- int id = trie[at_trie][c - 'a'];
- res += rec(at + 1, (visited | at_trie_is_end_of_word[id]), id);
- }
- return dp[at][visited][at_trie] = res;
- }
- void generate_strings(int at, int visited, int at_trie, string tmp) {
- if(at == o and __builtin_popcount(visited) == n) {
- cout << tmp << endl;
- return;
- }
- if(at >= o) {
- return;
- }
- for(char c = 'a'; c <= 'z'; c++) {
- int id = trie[at_trie][c - 'a'];
- if(rec(at + 1, visited | at_trie_is_end_of_word[id], id) > 0) {
- generate_strings(at + 1, visited | at_trie_is_end_of_word[id], id, tmp + c);
- }
- }
- }
- int main() {
- ios_base::sync_with_stdio(false);
- cin >> o >> n;
- memset(dp, -1, sizeof dp);
- vector<string> v(n);
- for(int i = 0; i < n; i++) {
- cin >> v[i];
- }
- int idx = 1;
- map<string, int> m1;
- map<int, string> m2;
- for(int i = 0; i < n; i++) {
- string tmp = "";
- for(int j = 0; j < (int) v[i].size(); j++) {
- tmp += v[i][j];
- m1[tmp] = idx;
- m2[idx] = tmp;
- idx++;
- }
- }
- m1[""] = 0;
- m2[0] = "";
- for(int i = 0; i <= 100; i++) {
- if(m2.find(i) != m2.end()) {
- for(int j = 0; j < n; j++) {
- if((int) m2[i].size() >= (int) v[j].size() and m2[i].find(v[j]) != string::npos) {
- at_trie_is_end_of_word[i] |= (1 << j);
- }
- }
- }
- string tmp = "";
- for(char c = 'a'; c <= 'z'; c++) {
- tmp = m2[i] + c;
- while(m1.find(tmp) == m1.end()) {
- tmp.erase(tmp.begin());
- }
- trie[i][c - 'a'] = m1[tmp];
- }
- }
- ll res = rec(0, 0, 0);
- cout << res << endl;
- if(res < 30) {
- generate_strings(0, 0, 0, "");
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement