UVA - 1401 | LA 3942 - Remember the Word(dp+trie)

时间:2023-03-08 16:15:22

https://vjudge.net/problem/UVA-1401

题意

给出S个不同的单词作为字典,还有一个长度最长为3e5的字符串。求有多少种方案可以把这个字符串分解为字典中的单词。

分析

首先强烈吐槽,vjudge上的UVALive 3942怎么都过不了。。。然而题目一模一样的UVA 1401就稳稳地过了。。。很玄学。

根据题意可以想到一个dp,dp[i]表示从第i个字符开始的字符串的分解方案。那么dp[i]=dp[i]+dp[i+len(x)],其中单词x为匹配的前缀。

如此,从后开始枚举i,每次都走一遍trie,找对应前缀的单词节点,然后计数。初始化dp[len]=1,为了让dp[len-1]能正确转移。

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <string>
#include <algorithm>
#include <cmath>
#include <ctime>
#include <vector>
#include <queue>
#include <map>
#include <stack>
#include <set>
#include <bitset>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define ms(a, b) memset(a, b, sizeof(a))
#define pb push_back
#define mp make_pair
#define pii pair<int, int>
//#define eps 0.0000000001
#define IOS ios::sync_with_stdio(0);cin.tie(0);
#define random(a, b) rand()*rand()%(b-a+1)+a
#define pi acos(-1)
//const ll INF = 0x3f3f3f3f3f3f3f3fll;
const int inf = 0x3f3f3f3f;
const int maxn = 3e5 + ;
const int maxm = 4e5 +;
const int mod = ;
const int sigma_size = ;
char s[maxn];
ll dp[maxn];
struct Trie{
int ch[maxm][sigma_size];
bool val[maxm];
int sz;
void init(){
sz=;
memset(ch[],,sizeof(ch[]));
memset(val,,sizeof(val));
}
int idx(char c) { return c-'a'; }
void insert(char* s){
int u=,n=strlen(s);
for(int i=;i<n;i++){
int c = idx(s[i]);
if(!ch[u][c]){
memset(ch[sz],,sizeof(ch[sz]));
val[sz]=false;
ch[u][c]=sz++;
}
u=ch[u][c];
}
val[u]=true;
}
void query(char* s){
int len=strlen(s);
memset(dp,,sizeof(dp));
dp[len]=;
for(int i=len-;i>=;i--){
int u=;
for(int j=i;j<len;j++){
int c = idx(s[j]);
if(!ch[u][c]) break;
u=ch[u][c];
if(val[u]) dp[i]=(dp[i]+dp[j+])%mod;
}
}
}
};
Trie trie;
char tmp[];
int main() {
#ifdef LOCAL
freopen("in.txt", "r", stdin);
// freopen("input.txt", "w", stdout);
#endif
int cas=;
while(~scanf("%s",s)){
trie.init();
int n;
scanf("%d",&n);
for(int i=;i<n;i++){
scanf("%s",tmp);
trie.insert(tmp);
}
trie.query(s);
printf("Case %d: %lld\n",cas++,dp[]);
}
return ;
}