解題區/解題區 - UVa

UVa 12785 - Emacs Plugin

contents

  1. 1. Problem
  2. 2. Sample Input
  3. 3. Sample Output
  4. 4. Solution

Problem

每個 * 位置，可以任意替換成任何字串或者是空字串，是問是否有可能匹配主字串。

Sample Input

1
2
3
4
5
6
7
8
9
4
heyhelloyou
hel*
*o*e
e*o
hello
1
hello
x

Sample Output

1
2
3
4
5
yes
no
yes
yes
no

Solution

以 * 劃分，將其切割成好幾個 token，根據貪心原則只要按照順序出現這些 token 即可，因此盡可能靠左。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
#include <stdio.h>
#include <string.h>
#include <iostream>
#include <sstream>
using namespace std;
#define MAXN 100005
char P[MAXN], T[MAXN];
int kmpTable[MAXN];
void KMPtable(const char *P, int len) {
    int i, j;
    kmpTable[0] = -1, i = 1, j = -1;
    while(i < len) {
        while(j >= 0 && P[j+1] != P[i])
            j = kmpTable[j];
        if(P[j+1] == P[i])
            j++;
        kmpTable[i++] = j;
    }
}
int KMPmatching(const char *T, int tlen, const char *P, int plen) {
    for(int i = 0, j = -1; i < tlen; i++) {
        while(j >= 0 && P[j+1] != T[i])
            j = kmpTable[j];
        if(P[j+1] == T[i])  j++;
        if(j == plen-1)
        	return i;
    }
    return -1;
}
int main() {
//	freopen("in.txt", "r+t", stdin);
//	freopen("out.txt", "w+t", stdout); 
    int n, plen, tlen;
    string token;
    while (scanf("%d", &n) == 1) {
        while (getchar() != '\n');
        gets(P);
        plen = strlen(P);
        for (int i = 0; i < n; i++) {
            gets(T);
            for (int j = 0; T[j]; j++) {
                if (T[j] == '*')
                    T[j] = ' ';
            }
            stringstream sin(T);
            int start = 0;
            while (sin >> token) {		
                KMPtable(token.c_str(), token.length());
                int test = KMPmatching(P + start, plen - start, token.c_str(), token.length());
//				printf("%s %d %s\n", token.c_str(), test, P + start);
                if (test == -1)	 {start = -1; break;}
                start += test + 1;
            }
            puts(start == -1 ? "no" : "yes");
        }
    }
    return 0;
}
/*
4
heyhelloyou
hel*
*o*e
e*o
hello
1
hello
x
10
rwoeyhtdvtswftfguuujqxdxdqylkyqaahianzbejckxbgeybq
oexktdvtswftf*w*n*q*rvdloll*qr
kdd*ts*ftv**ur**cdx*qi
*dtlk
**q**g****a**n
*/