14b.c

   1 #include <stdio.h>
   2 #include <stdbool.h>
   3 #include <limits.h>
   4 #include <string.h>
   5
   6 struct template { char x1; char x2; char ins; };
   7
   8 #define lookup(i, x1, x2) (i)[((x1)-'A')+((x2)-'A')*26]
   9
  10 int main()
  11 {
  12         char *buf = NULL;
  13         size_t len;
  14         int ntemplate = 0;
  15         struct template template[100];
  16         unsigned long input1[26*26] = {0}, input2[26*26] = {0};
  17         unsigned long *input = input1, *newinput = input2;
  18
  19         int first = getchar();
  20         int c, last = first;
  21         unsigned long freq[26] = {0};
  22         while ( (c = getchar()) != '\n') {
  23                 lookup(input, last, c) = 1;
  24                 last = c;
  25         }
  26
  27         while (getline(&buf, &len, stdin) != -1) {
  28                 if (buf[0] == '\n')
  29                         continue;
  30                 template[ntemplate++] = (struct template)
  31                         {.x1=buf[0], .x2=buf[1], .ins=buf[6]};
  32         }
  33
  34         for (int step = 0; step < 40; step++) {
  35                 for (int i = 0; i<ntemplate; i++) {
  36                         struct template t = template[i];
  37                         unsigned long freq = lookup(input, t.x1, t.x2);
  38                         lookup(newinput, t.x1, t.ins) += freq;
  39                         lookup(newinput, t.ins, t.x2) += freq;
  40                 }
  41                 unsigned long *t = newinput;
  42                 newinput = input;
  43                 input = t;
  44                 memset(&newinput[0], 0, sizeof(input1));
  45         }
  46
  47         for (char x = 'A'; x<='Z'; x++) {
  48                 for (char y = 'A'; y<='Z'; y++) {
  49                         freq[x-'A'] += lookup(input, x, y);
  50                         freq[y-'A'] += lookup(input, x, y);
  51                 }
  52         }
  53         freq[first-'A']++;
  54         freq[last-'A']++;
  55
  56         unsigned long min = ULONG_MAX, max = 0;
  57         for (int i = 0; i<26; i++) {
  58                 max = freq[i] > max ? freq[i] : max;
  59                 min = freq[i] > 1 && freq[i] < min ? freq[i] : min;
  60         }
  61
  62         printf("%lu\n", max/2-min/2);
  63 }