Advertisement
Guest User

Untitled

a guest
Jul 31st, 2015
197
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.89 KB | None | 0 0
  1. #include <iostream>
  2. #include <cstdio>
  3. #include <cstdlib>
  4. #include <vector>
  5. #include <set>
  6. #include <map>
  7. #include <cstring>
  8. #include <string>
  9. #include <cmath>
  10. #include <ctime>
  11. using namespace std;
  12.  
  13.  
  14. #ifdef LOCAL
  15.     #define eprintf(...) fprintf(stderr, __VA_ARGS__)
  16. #else
  17.     #define eprintf(...) 42
  18. #endif
  19.  
  20. const int maxn = (int) 205;
  21. const int maxk = (int) 2e5 + 100;
  22.  
  23. int nxt[maxk][26];
  24. bool used[maxk][maxn][2];
  25. int ans[maxn][maxn];
  26. int sz = 1;
  27. int timer = 146;
  28. char word[maxn][maxn];
  29.  
  30. char str[maxn];
  31.  
  32. void cp(int id)
  33. {
  34.     int pos = 0;
  35.     while (true)
  36.     {
  37.         str[pos] = word[id][pos];
  38.         if (str[pos] == 0)
  39.             break;
  40.         pos++;
  41.     }
  42. }
  43.  
  44. void addWord(string s, int id, int cd)
  45. {
  46.     eprintf("%s %d\n", s.c_str(), cd);
  47.     int len = (int) s.length();
  48.     int pos = 0;
  49.     for (int i = 0; i < len; i++)
  50.     {
  51.         int ch = s[i] - 'a';
  52.         if (nxt[pos][ch] == 0)
  53.         {
  54.             nxt[pos][ch] = sz++;
  55.         }
  56.         pos = nxt[pos][ch];
  57.     }
  58.     used[pos][id][cd] = true;
  59. }
  60.  
  61. void addWord(int id)
  62. {
  63.     scanf("%s", word[id] );
  64.     eprintf("adding %s:\n", word[id] );
  65.     int len = (int) strlen(word[id] );
  66.     addWord(string(word[id] ), id, 0);
  67.  
  68.     for (int pos = 0; pos < len; pos++)
  69.         for (char ch = 'a'; ch <= 'z'; ch++)
  70.         {
  71.             cp(id);
  72.             str[pos] = ch;
  73.             addWord(string(str), id, 1);
  74.         }
  75.     for (int pos = 0; pos < len - 1; pos++)
  76.     {
  77.         cp(id);
  78.         swap(str[pos], str[pos + 1] );
  79.         addWord(string(str), id, 1);
  80.     }
  81.     for (int pos = 0; pos <= len; pos++)
  82.     {
  83.         cp(id);
  84.         for (int i = len; i > pos; i--)
  85.         {
  86.             str[i] = str[i - 1];
  87.         }
  88.         str[len + 1] = 0;
  89.         for (char ch = 'a'; ch <= 'z'; ch++)
  90.         {
  91.             str[pos] = ch;
  92.             addWord(string(str), id, 1);
  93.         }
  94.     }
  95.     for (int pos = 0; pos < len; pos++)
  96.     {
  97.         cp(id);
  98.         for (int i = pos; i < len; i++)
  99.         {
  100.             str[i] = str[i + 1];
  101.         }
  102.         str[len - 1] = 0;
  103.         addWord(string(str), id, 1);
  104.     }
  105.  
  106. }
  107.  
  108. void getAns(int n, int d)
  109. {
  110.     timer++;
  111.     for (int i = 0; i < sz; i++)
  112.         for (int a = 0; a < n; a++)
  113.             for (int ad = 0; ad <= 1; ad++)
  114.                 for (int bd = 0; bd <= 1 && ad + bd <= d; bd++)
  115.                 {
  116.                     if (!used[i][a][ad] )
  117.                         continue;
  118.                     for (int b = a + 1; b < n; b++)
  119.                         if (used[i][b][bd] )
  120.                             ans[a][b] = timer;
  121.                 }
  122.     int answer = 0;
  123.     for (int i = 0; i < n; i++)
  124.         for (int j = i + 1; j < n; j++)
  125.             if (word[i][j] )
  126.             {
  127.                 printf("%s,%s\n", word[i], word[j] );
  128.                 answer++;
  129.             }
  130.     printf("%d\n", answer);
  131. }
  132.  
  133. void clear(int n)
  134. {
  135.     for (int i = 0; i < sz; i++)
  136.     {
  137.         for (int j = 0; j < n; j++)
  138.             used[i][j][0] = used[i][j][1] = false;
  139.         memset(nxt[i], 0, sizeof nxt[i] );
  140.     }
  141.     sz = 1;
  142. }
  143.  
  144.  
  145. bool solve()
  146. {
  147.     int n, d;
  148.     scanf("%d", &n);
  149.     if (n == 0)
  150.         return false;
  151.     scanf("%d", &d);
  152.    
  153.     for (int i = 0; i < n; i++)
  154.     {
  155.         addWord(i);
  156.     }
  157.  
  158.     getAns(n, d);
  159.  
  160.     clear(n);
  161.     return true;
  162. }
  163.  
  164. int main()
  165. {
  166. #ifdef LOCAL
  167.     freopen ("input001.txt", "r", stdin);
  168.     freopen ("output.txt", "w", stdout);
  169. #endif
  170.     while (solve() ) {}
  171.    
  172.     return 0;
  173. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement