标题：通配符的等价转换
出处：Felix021
时间：Mon, 09 Jun 2008 00:35:58 +0000
作者：felix021
地址：https://www.felix021.com/blog/read.php?971

内容：
WHUACM 20080608 DAY4个人赛A题

描述：通配符*代表0个或多个字符，?代表不多不少正好一个字符。*和?的某些组合是等价的，比如*??*和?*?等价。给出一串只包含a-z、A-Z、*、?的字符串，把它转换成最短小的等效字符串——注意这里的小：比如*?比?*小。

分析：
一个由*和?组成的字符串可以有无限多个不同的等效字符串，所以我们要找出一个容易用数据表示出来的中间状态，把任意一个状态都转换成这种状态，然后再由这种状态出发根据一定的规则生成要找的最短小的等效字符串。
分析*和?的特点可知：*表示的数量是不定的，任意个*和一个*等价；?表示的数量是固定的，一个?只和一个?等价。
从这点出发，我们可以设计一个状态：

struct state1{int count_ast, count_que;};


state1里分别记录了星号和问号的数量，但是它比较表面化，还不够精炼。
因为任意个*和一个*等价，所以可以把状态这样记录：

struct state2{bool ast_exists; int count_que;};


state2里记录了是否出现星号，以及问号的数量。
这可以用更通俗的人类语言描述：记录了 “至少多少个字符” 或是 “恰好多少个字符”。

于是我们可以根据state2设计出最短小的等效字符串：
如果原字符串有星号出现，最短小等效字符串必然有一个星号（至少）；否则最短小字符串就没有星号（恰好）。
原字符串有多少个问号，最短小字符串也有多少个问号（多少个字符）。
因为星号的权值小于问号，所以星号放在所有问号的前面。

贴出我的代码吧：

#include<stdio.h>
#include<string.h>

int main(){
  int cases, i, j, k, type, min;
  char s[1010], d[1010], t;
  scanf("%d", &cases);
  while(cases--){
    scanf("%s", s);
    i = 0, j = 0;
    while(s[i] != 0){//处理字符串 
      if(s[i] == '*' || s[i] == '?'){//通配符
        type = 0; //等于状态 
        min = 0; //等价字符数 
        while(s[i] != 0 && (s[i] == '*' || s[i] == '?')){
          if(s[i] == '*'){
            type = 1; //至少状态 
          }else{
            min++;
          } 
          i++;
        }
        if(type == 1){
          d[j] = '*';
          j++;
        }
        for(k = 0; k < min; k++){
          d[j] = '?';
          j++;
        }
      }else{//普通字符 
        d[j] = s[i];
        i++, j++;
      }
    }
    d[j] = 0;
    printf("%s\n", d);
  }
  return 0;
}



Generated by Bo-blog 2.1.0