Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <cstdio>
- #include <cstdlib>
- #include <vector>
- #include <set>
- #include <map>
- #include <cstring>
- #include <string>
- #include <cmath>
- #include <ctime>
- using namespace std;
- #ifdef LOCAL
- #define eprintf(...) fprintf(stderr, __VA_ARGS__)
- #else
- #define eprintf(...) 42
- #endif
- const int maxn = (int) 205;
- const int maxk = (int) 2e5 + 100;
- int nxt[maxk][26];
- bool used[maxk][maxn][2];
- int ans[maxn][maxn];
- int sz = 1;
- int timer = 146;
- char word[maxn][maxn];
- char str[maxn];
- void cp(int id)
- {
- int pos = 0;
- while (true)
- {
- str[pos] = word[id][pos];
- if (str[pos] == 0)
- break;
- pos++;
- }
- }
- void addWord(string s, int id, int cd)
- {
- eprintf("%s %d\n", s.c_str(), cd);
- int len = (int) s.length();
- int pos = 0;
- for (int i = 0; i < len; i++)
- {
- int ch = s[i] - 'a';
- if (nxt[pos][ch] == 0)
- {
- nxt[pos][ch] = sz++;
- }
- pos = nxt[pos][ch];
- }
- used[pos][id][cd] = true;
- }
- void addWord(int id)
- {
- scanf("%s", word[id] );
- eprintf("adding %s:\n", word[id] );
- int len = (int) strlen(word[id] );
- addWord(string(word[id] ), id, 0);
- for (int pos = 0; pos < len; pos++)
- for (char ch = 'a'; ch <= 'z'; ch++)
- {
- cp(id);
- str[pos] = ch;
- addWord(string(str), id, 1);
- }
- for (int pos = 0; pos < len - 1; pos++)
- {
- cp(id);
- swap(str[pos], str[pos + 1] );
- addWord(string(str), id, 1);
- }
- for (int pos = 0; pos <= len; pos++)
- {
- cp(id);
- for (int i = len; i > pos; i--)
- {
- str[i] = str[i - 1];
- }
- str[len + 1] = 0;
- for (char ch = 'a'; ch <= 'z'; ch++)
- {
- str[pos] = ch;
- addWord(string(str), id, 1);
- }
- }
- for (int pos = 0; pos < len; pos++)
- {
- cp(id);
- for (int i = pos; i < len; i++)
- {
- str[i] = str[i + 1];
- }
- str[len - 1] = 0;
- addWord(string(str), id, 1);
- }
- }
- void getAns(int n, int d)
- {
- timer++;
- for (int i = 0; i < sz; i++)
- for (int a = 0; a < n; a++)
- for (int ad = 0; ad <= 1; ad++)
- for (int bd = 0; bd <= 1 && ad + bd <= d; bd++)
- {
- if (!used[i][a][ad] )
- continue;
- for (int b = a + 1; b < n; b++)
- if (used[i][b][bd] )
- ans[a][b] = timer;
- }
- int answer = 0;
- for (int i = 0; i < n; i++)
- for (int j = i + 1; j < n; j++)
- if (word[i][j] )
- {
- printf("%s,%s\n", word[i], word[j] );
- answer++;
- }
- printf("%d\n", answer);
- }
- void clear(int n)
- {
- for (int i = 0; i < sz; i++)
- {
- for (int j = 0; j < n; j++)
- used[i][j][0] = used[i][j][1] = false;
- memset(nxt[i], 0, sizeof nxt[i] );
- }
- sz = 1;
- }
- bool solve()
- {
- int n, d;
- scanf("%d", &n);
- if (n == 0)
- return false;
- scanf("%d", &d);
- for (int i = 0; i < n; i++)
- {
- addWord(i);
- }
- getAns(n, d);
- clear(n);
- return true;
- }
- int main()
- {
- #ifdef LOCAL
- freopen ("input001.txt", "r", stdin);
- freopen ("output.txt", "w", stdout);
- #endif
- while (solve() ) {}
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement