HDU 3901 Wildcard

Wildcard

Time Limit: 1000ms

Memory Limit: 65536KB

This problem will be judged on HDU. Original ID: 3901
64-bit integer IO format: %I64d Java class name: Main

When specifying file names (or paths) in DOS, Microsoft Windows and Unix-like operating systems, the asterisk character (“*") substitutes for any zero or more characters, and thequestion mark (“?") substitutes for any one character.
Now give you a text and a pattern, you should judge whether the pattern matches the text or not.

Input

There are several cases. For each case, only two lines. The first line contains a text, which contains only lower letters. The last line contains a pattern, which consists of lower letters and the two wildcards (“*", "?").
The text is a non-empty string and its size is less than 100,000, so do the pattern.

We ensure the number of “?” and the number of “*” in the pattern are both no more than 10.

Output

Output “YES” if the pattern matches the text, otherwise “NO”.

Sample Input

abcdef
a*c*f

Sample Output

YES

Source

2011 Multi-University Training Contest 7 - Host by ECNU

解题：AC自动机

参考这位大神的解法

  1 #include <bits/stdc++.h>
  2 using namespace std;
  3 const int maxn = 200005;
  4 vector<int>pos[maxn];
  5 int node[maxn][26],fail[maxn],tot,cnt;
  6 char wild[maxn],str[maxn],tmp[maxn];
  7 void build(char *s) {
  8     int root = tot = cnt = 0;
  9     memset(node[0],0,sizeof node[0]);
 10     pos[0].clear();
 11     for(int i = 0; !i || s[i-1]; ++i) {
 12         if(s[i] == '?' || s[i] == 0) {
 13             if(root) {
 14                 pos[root].push_back(i-1);
 15                 root = 0;
 16                 ++cnt;
 17             }
 18             continue;
 19         }
 20         int c = s[i] - 'a';
 21         if(!node[root][c]) {
 22             node[root][c] = ++tot;
 23             memset(node[tot],0,sizeof node[tot]);
 24             pos[tot].clear();
 25         }
 26         root = node[root][c];
 27     }
 28 }
 29 queue<int>q;
 30 void getFail() {
 31     while(!q.empty()) q.pop();
 32     for(int i = 0; i < 26; ++i)
 33         if(node[0][i]) {
 34             q.push(node[0][i]);
 35             fail[node[0][i]] = 0;
 36         }
 37     while(!q.empty()) {
 38         int u = q.front();
 39         q.pop();
 40         for(int i = 0; i < 26; ++i) {
 41             if(node[u][i]) {
 42                 q.push(node[u][i]);
 43                 int v = node[u][i];
 44                 fail[v] = node[fail[u]][i];
 45                 if(pos[fail[v]].size())
 46                     pos[v].insert(pos[v].end(),pos[fail[v]].begin(),pos[fail[v]].end());
 47             } else node[u][i] = node[fail[u]][i];
 48         }
 49     }
 50 }
 51 int x[maxn];
 52 int Find(char *s,int root = 0) {
 53     if(!cnt) return 0;
 54     for(int i = 0; s[i]; ++i) {
 55         root = node[root][s[i] - 'a'];
 56         x[i] = 0;
 57         for(int j = 0; j < pos[root].size(); ++j)
 58             if(i >= pos[root][j]) {
 59                 ++x[i - pos[root][j]];
 60                 if(x[i - pos[root][j]] == cnt)
 61                     return i - pos[root][j];
 62             }
 63     }
 64     return -1;
 65 }
 66 bool match(int slen,int plen) {
 67     int letter = 0,s = -1;
 68     for(int i = 0; i < plen; ++i)
 69         letter += (wild[i] != '*');
 70     if(letter > slen) return false;
 71     for(int i = 0; str[i]; ++i) {
 72         if(wild[i] == '?' || str[i] == wild[i]) continue;
 73         if(wild[i] == '*') s = i + 1;
 74         else return false;
 75         break;
 76     }
 77     if(s == -1) return true;
 78     for(int i = slen-1,j = plen-1; ; --i,--j) {
 79         if(i == -1 && j == -1) break;
 80         if(i == -1) {
 81             if(wild[j] != '*') return false;
 82             break;
 83         }
 84         if(j == -1) return false;
 85         if(wild[j] == '?' || str[i] == wild[j])
 86             wild[j] = str[slen = i] = 0;
 87         else if(wild[j] == '*') break;
 88         else return false;
 89     }
 90 
 91     int st = s - 1;
 92     for(int i = 1; i < plen - letter; ++i) {
 93         if(wild[s] == '*') {
 94             ++s;
 95             continue;
 96         }
 97         int len = 0;
 98         while(wild[s] != '*' && wild[s]) {
 99             tmp[len++] = wild[s++];
100             tmp[len] = 0;
101         }
102         build(tmp);
103         getFail();
104         int ps = Find(st + str);
105         if(ps == -1) return false;
106         st += ps + len;
107         if(st > slen) return false;
108     }
109     return true;
110 }
111 int main() {
112     while(~scanf("%s%s",str,wild)) {
113         bool flag = match(strlen(str),strlen(wild));
114         puts(flag?"YES":"NO");
115     }
116     return 0;
117 }

View Code