Advertisement
Guest User

Untitled

a guest
Aug 17th, 2017
71
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.17 KB | None | 0 0
  1. #include <cstdio>
  2. #include <cstring>
  3. #include <algorithm>
  4.  
  5. #define MAX 10000
  6.  
  7. using namespace std;
  8.  
  9. char prods[MAX][30], ans[MAX][30];
  10. int N, L;
  11.  
  12. int dist (char *s1, char *s2, int len1, int len2)
  13. {
  14.     int ret[30][30], minimum = -1;
  15.    
  16.     for (int i = 0; i < len1; i++)
  17.         ret[i][0] = i;
  18.        
  19.     for (int i = 0; i < len2; i++)
  20.         ret[0][i] = i;
  21.        
  22.     for (int i = 0; i < len1; i++)
  23.         for (int k = 0; k < len2; k++)
  24.         {
  25.             if (s1[i] == s2[k])
  26.                 ret[i][k] = ret[i - 1][k - 1];
  27.             else
  28.             {
  29.                 minimum = min (ret[i - 1][k] + 1, ret[i][k - 1] + 1);
  30.                 ret[i][k] = min (minimum, ret[i - 1][k - 1] + 1);
  31.             }
  32.         }
  33.        
  34.     return ret[len1 - 1][len2 - 1];
  35. }
  36.  
  37. void input ()
  38. {
  39.     char alarm_code[30];
  40.     int n = 0;
  41.    
  42.     scanf ("%d", &N);
  43.     for (int k = 0; k < N; k++)
  44.         scanf ("%s", prods[k]);
  45.        
  46.     scanf ("%d", &L);
  47.     for (int k = 0; k < L; k++)
  48.     {
  49.         scanf ("%s", alarm_code);
  50.         for (int i = 0; i < N; i++)
  51.             if (dist (prods[i], alarm_code, strlen (prods[i]), strlen (alarm_code)) == 1)
  52.             {
  53.                 strcpy (ans[n++], alarm_code);
  54.                 break;
  55.             }
  56.     }
  57.    
  58.     printf ("%d\n", n);
  59.     for (int k = 0; k < n; k++)
  60.         printf ("%s\n", ans[k]);
  61. }
  62.  
  63. int main ()
  64. {
  65.     input ();
  66.    
  67.     return 0;
  68. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement