Day 0x17 UVa10252 Common Permutation

• Virtual Judge
• ZeroJudge

题意

• 输入 a、b 两字串，输出皆为两者的子字串
• 需要注意的有：
  1. 重复输入两字串 (各一行)
  2. 字串皆小写字母
  3. 输出的字串要同时为两字串的子字串 (可顺序不同)
  4. 承上点，有多组符合输出字母由小到大

解法

• 换句话说，确定两字串的字母各有多少个，由小到大输出即可，和 Day 0x5 UVa10062 Tell me the frequencies! & Day 0x6 UVa10008 What's Cryptanalysis? 这两题小类似
• 重复读入两字串直到 EOF，并用两次回圈分别计算两字串各字母的出现次数

  char a[1001] = {0};
  char b[1001] = {0};
  int i, j;
  
  while(gets(a) && gets(b)){
  
      int tableA[26] = {0};
      int tableB[26] = {0};
  
      for(i = 0; i < strlen(a); i++){
          tableA[a[i] - 'a']++;
      }
      for(i = 0; i < strlen(b); i++){
          tableB[b[i] - 'a']++;
      }
      ...
  }
  

• 先 for 回圈由小到大遍历字母表，透过 if 比较两字串该字母出现的次数谁比较少，再用 for 输出较少刺数的字母

  for(i = 0; i < 26; i++){
      if(tableA[i] != 0 && tableB[i] != 0){
          if(tableA[i] <= tableB[i]){
              min = tableA[i];
          }
          else{
              min = tableB[i];
          }
          for(j = 0; j < min; j++){
              printf("%c", i + 97);
          }
      }
  }
  

• C code

  #include<stdio.h>
  #include<string.h>
  
  int main(){
  
      char a[1001] = {0};
      char b[1001] = {0};
      int i, j;
      int length;
      int min;
  
      while(gets(a) && gets(b)){
  
          int tableA[26] = {0};
          int tableB[26] = {0};
  
          for(i = 0; i < strlen(a); i++){
              tableA[a[i] - 'a']++;
          }
          for(i = 0; i < strlen(b); i++){
              tableB[b[i] - 'a']++;
          }
  
          for(i = 0; i < 26; i++){
              if(tableA[i] && tableB[i]){
                  if(tableA[i] <= tableB[i]){
                      min = tableA[i];
                  }
                  else{
                      min = tableB[i];
                  }
                  for(j = 0; j < min; j++){
                      printf("%c", i + 97);
                  }
              }
          }
  
          printf("\n");
  
      }
  
      return 0;
  }