解題區/解題區 - UVa

UVa 11539 - Another Word Game

contents

  1. 1. Problem
  2. 2. Input
  3. 3. Output
  4. 4. Sample Input
  5. 5. Output for Sample Input
  6. 6. Solution

Problem

This is just another word game. You are given a dictionary of words. Each of the word has a weight W, which is an integer value. You are given another string S. Initially your score is zero. In each turn you can mark some consecutive characters. If these consecutive characters create a word in the given dictionary, corresponding weight will be added to your score, otherwise a penalty P will be subtracted word length times from your score. Here word length is number of character in a word, and P is an integer value. What is the maximum score you can gain?

Note that your have to make a move until all characters of S are marked, and you cannot mark one character more than once.

Input

Input will start with an integer number T (T≤20), which indicates the number of test case. Each test case starts with two integer N (N ≤ 10000) and P (0 ≤ P ≤ 10000). Here N is the number of words in the dictionary and P is the value of Penalty. Each of the next N lines will contain a word and corresponding integer weight W (0 ≤ W ≤ 10000). No word of this dictionary will contain more than 100 characters, and a word will only contain lower case alphabet (‘a’, ‘b’, … ,’z’). The last line of the input will contain string S. S will not contain more than 10000 characters, and will contain only lower case letters.

Output

For each test case you have to output one line which “Case #:” where # is replaced by the case number, then a space, then the maximum score.

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
3
2 5
ab 2
cd 3
abcd
3 5
ab 2
cd 3
bc 16
abcd
1 100
abd 1
abcd

Output for Sample Input

1
2
3
Case 1: 5
Case 2: 6
Case 3: -400

Solution

題目描述：

給一個主子串 S，可以由其他小字串組合而成，這些小字串可以重複使用，每次使用可以得到相對應的單位獲益，但它們彼此之間不能重疊，如果 S 有一個字符沒有匹配，將會被罰款 W 單位。

求一個最高獲益的值為何？

題目解法：

由於考慮 dp[i] 已經匹配長度為 i 的時候，轉移會在字串匹配的時候速度非常慢，因此可以利用字串匹配的特性，對於所有小字串建一個 trie，接著建造出 AC 自動機，可以藉由失敗指針中快速找到當前有多少可以轉移的字符串可以串接。

但問題可能會在小字串長度太長效率下降，AC 只是剛好！也有人直接用 trie 搭配走訪就過去了，對於位置 i，從 root 開始往下走，一直走到位置 j，並且轉移，直到 trie 沒辦法走下去，保證不會有其他匹配情況。

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
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <queue>
#include <map>
#define maxKind 26
using namespace std;
struct Node{
    Node *fail;
    Node *next[maxKind];
    int cnt;
    vector< pair<int, int> > attr;
    Node() {
        fail = NULL;
        cnt = 0;
        memset(next, 0, sizeof(next));
    }
};
void build_Trie(const char* str, Node *root, pair<int, int> val) {
    Node *p = root;
    int i = 0, idx;
    while(str[i]) {
        idx = str[i] - 'a';
        if(p->next[idx] == NULL)
            p->next[idx] = new Node();
        p = p->next[idx];
        i++;
    }
    p->cnt++;
    p->attr.push_back(val);
}
void build_AC_automation(Node *root) {
    root->fail = NULL;
    queue<Node*> Q;
    Q.push(root);
    Node *tn, *p;
    while(!Q.empty()) {
        tn = Q.front();
        Q.pop();
        for(int i = 0; i < maxKind; i++) {
            if(tn->next[i] == NULL)
                continue;
            Q.push(tn->next[i]);
            p = tn->fail;
            while(p != NULL && p->next[i] == NULL)
                p = p->fail;
            if(p == NULL)
                tn->next[i]->fail = root;
            else
                tn->next[i]->fail = p->next[i];
        }
    }
}
void free_AC_automation(Node *root) {
    queue<Node*> Q;
    Q.push(root);
    Node *tn, *p;
    while(!Q.empty()) {
        tn = Q.front();
        Q.pop();
        for(int i = 0; i < maxKind; i++) {
            if(tn->next[i] != NULL) {
                Q.push(tn->next[i]);
            }
        }
        free(tn);
    }
}
void query(const char* str, Node *root, int P) {
    Node *tn = root, *p;
    int n = strlen(str);
    int dp[100005] = {};
    for(int i = 0, idx; i < n; i++) {
        idx = str[i] - 'a';
        dp[i + 1] = dp[i] - P;
        while(tn->next[idx] == NULL && tn != root)
            tn = tn->fail;
        tn = tn->next[idx];
        tn = (tn == NULL) ? root : tn;
        p = tn;
        while(p != root) {
            if(p->cnt) {
            	for(vector< pair<int, int> >::iterator it = p->attr.begin();
                    it != p->attr.end(); it++) {
                    dp[i + 1] = max(dp[i + 1], dp[i - it->first + 1] + it->second);
                }
            }
            p = p->fail;
        }
    }
    printf("%d\n", dp[n]);
}
char buf[100001];
int main() {
    int testcase, N, P, val, cases = 0;
    scanf("%d", &testcase);
    while(testcase--) {
        Node *root = new Node();
        
        scanf("%d %d", &N, &P);
        for(int i = 0; i < N; i++) {
        	scanf("%s %d", buf, &val);
            build_Trie(buf, root, make_pair(strlen(buf), val));
        }
        
        build_AC_automation(root);
        scanf("%s", buf);
        printf("Case %d: ", ++cases);
        query(buf, root, P);
        free_AC_automation(root);
    }
    return 0;
}