首页 > 代码库 > UVA3942 Remember the Word
UVA3942 Remember the Word
题意：输入一个字符串(l<300000)，一个n(n<4000)，接下来n个字符串(l<100)，问能分解成几种字符串
题解：直接计算复杂度高，考虑DP，dp[i]代表以第i个字符开头的字符串分解的方案数，dp[i] = sum(dp[j+len])，len代表可以找到的字符串长度，多模式的字符串用到了char树，放在char树上跑一遍，找到以i+1开头的字符串复杂度,一开始写搜索。。后来发现复杂度过不去
#include <bits/stdc++.h>#define ll long long#define maxn 100*4000+10#define siz 26#define mod 20071027using namespace std;char s[300010], s1[110];ll l, dp[300010];struct Tire{ ll ch[maxn][siz]; ll val[maxn], sz;//节点总数 Tire(){sz = 1;memset(ch, 0, sizeof(ch));} ll idx(char c){return c-‘a‘;} void insert(char *s, ll v){ ll u = 0,n = strlen(s); for(ll i=0;i<n;i++){ ll c = idx(s[i]); if(!ch[u][c]){ memset(ch[sz], 0, sizeof(ch[sz])); val[sz] = 0; ch[u][c] = sz++; } u = ch[u][c]; } val[u] = v; }}Tir;int main(){ ll n, t = 0; while(~scanf("%s", s)){ l = strlen(s); memset(Tir.ch, 0, sizeof(Tir.ch)); Tir.sz = 1; memset(dp, 0, sizeof(dp)); dp[l] = 1; scanf("%lld", &n); for(ll i=1;i<=n;i++){ scanf("%s", s1); Tir.insert(s1, i); } for(int i=l-1;i>=0;i--){ int u = 0; for(int j=i;j<l;j++){ if(Tir.ch[u][s[j]-‘a‘]==0) break; u = Tir.ch[u][s[j]-‘a‘]; if(Tir.val[u]) dp[i] = (dp[i]+dp[j+1])%mod; } } printf("Case %lld: %lld\n", ++t, dp[0]); } return 0;}
UVA3942 Remember the Word
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。