【UVALive-3942】解题报告（字典树，dp）

原始题目

题目大意

  • 给定一个文本串和n个字符串，用这n个字符串组合成文本串有多少种可能。

解题思路

  • 先将n个字符串储存到字典树里。
  • 考虑DP
    • \(dp[i]\)表示前i位字符进行第一次分割的可能数目
    • i从len-1->0逆序遍历，j从i到len-1遍历。
    • 只要遍历j时遇到染色结点，表明可以在此再分割一次，由此推出状态转移方程。\(dp[i] = (dp[i] + dp[j + 1]) % mod\)

解题代码

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
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
#include <cstdio>
#include <cstring>
#include <iostream>
#include <cstdlib>
#include <set>
#include <string>
#include <cstring>
#include <stack>
#define rep(i,a,n) for(int i=a;i<n;i++)
#define per(i,a,n) for(int i=n-1;i>=a;i--)
#define ms(x,a) memset((x),(a),sizeof(x))
using namespace std;
const int maxn=3e5+5;
const int maxl=26;
const int mod=20071027;
typedef long long ll;
typedef struct Trie
{
	int v;
	Trie* next[maxl];
}Trie;
 
Trie *root;



void iniTrie()
{
	root=(Trie*)malloc(sizeof(Trie));
	for(int i=0;i<maxl;i++)
		root->next[i]=NULL;
	root->v=-1;
}

void creTrie(char* a)
{
	int l=strlen(a);
	Trie *p=root,*q;
	for(int i=0;i<l;i++)
	{
		int id=a[i]-'a';
		//并非前缀不能有相同，而是不能在相同的分支上。 
		
		if(p->next[id]!=NULL) {
			p=p->next[id];
			if(i==l-1){
				p->v=1;
				return;
			}
		}
		else{
			q=(Trie*)malloc(sizeof(Trie));
			q->v=0;
			for(int j=0;j<maxl;j++) q->next[j]=NULL;
			p->next[id]=q;
			p=p->next[id];
			if(i==l-1){
				p->v=1;
				return;
			}
		}

	}

}

bool findTrie(string b){
	Trie *p=root;
	int l=b.length();
	for(int i=0;i<l;i++){
		int index=b[i]-'a';
		if(p->next[index]!=NULL)
			p=p->next[index];
		else return false;
	}
	return p->v;
}

void delTrie(Trie *p)  
{  
    int i;  
    for(i=0;i<maxl;i++)  
    {  
        if(p->next[i] != NULL)  
            delTrie(p->next[i]);  
    }  
    free(p);
//    printf("1");
	p==NULL;  
	return ;
}  
int n,kase;
int dp[maxn];
char raw[maxn],s[1000];

int Dp(char *s, int len) {

        dp[len] = 1;

        for (int i = len - 1; i >= 0; --i) {
            Trie *pp = root;//根节点
            for (int j = i; j < len; ++j) {
                int temp = s[j]-'a';
                //cout << s[j] << endl;
                if (pp->next[temp] == NULL) {//同dfs退出原理
                    break;
                }
                pp = pp->next[temp];
                if (pp->v == true) {
                    dp[i] = (dp[i] + dp[j + 1]) % mod;//更新方案数
                    //cout << j + 1 << " " << len << endl;
                }
            }
            dp[i] %= mod;
        }

        return dp[0];
    }

void solve(){
	int ans=0;
	int len=strlen(raw);
	ms(dp,0);
	ans=Dp(raw,len);
	cout << "Case " << ++kase << ": ";
	cout<<ans<<endl;
	
}


int main()
{
//	freopen("in.txt", "r", stdin);
	ios::sync_with_stdio(false);
	while(cin>>raw){
		iniTrie();
		cin>>n;
		rep(i,0,n){
			cin>>s;
			creTrie(s);
		}
		solve();
		delTrie(root);
	}
}

收获与反思

  • 字典树与dp结合
  • 记忆化，dp的思想很重要！