tyvj1102 单词的划分
2024-08-24 19:24:52
描述
有一个很长的由小写字母组成字符串。为了便于对这个字符串进行分析,需要将它划分成若干个部分,每个部分称为一个单词。出于减少分析量的目的,我们希望划分出的单词数越少越好。你就是来完成这一划分工作的。
输入格式
第一行,一个字符串。(字符串的长度不超过100)
第二行一个整数n,表示单词的个数。(n<=100)
第3~n+2行,每行列出一个单词。
第二行一个整数n,表示单词的个数。(n<=100)
第3~n+2行,每行列出一个单词。
输出格式
一个整数,表示字符串可以被划分成的最少的单词数。
测试样例1
输入
realityour
5
real
reality
it
your
our
输出
2
备注
(原字符串可拆成real+it+your或reality+our,由于reality+our仅为两个部分,因此最优解为2,另外注意,单词列表中的每个单词都可以重复使用多次,也可以不用)
#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;
const int sed = ,Sed = ,mod = ,Mod = ;
int n,m,dp[];
string a[],s;
vector<int> h[mod];
int main(){
cin>>s>>n;
for(int i = ;i <= n;i++){
cin>>a[i];
int hash = ,Hash = ;
for(int j = ;j < a[i].size();j++){
hash = (hash * sed + a[i][j]) % mod;
Hash = (Hash * Sed + a[i][j]) % Mod;
}
h[hash].push_back(Hash);
}
m = s.size();
for(int i = ;i <= m;i++) dp[i] = ;
for(int i = ;i <= m;i++){
for(int j = i;j >= ;j--){
int hash = ,Hash = ;
for(int k = j - ;k <= i - ;k++){
hash = (hash * sed + s[k]) % mod;
Hash = (Hash * Sed + s[k]) % Mod;
}
bool ok = false;
for(int k = ;k < h[hash].size();k++){
if(h[hash][k] == Hash){
ok = true;
break;
}
}
if(ok) dp[i] = min(dp[i],dp[j-] + );
}
}
cout<<dp[m];
return ;
}
最新文章
- Light OJ 1031 - Easy Game(区间dp)
- Linux基础2
- 装X之写博客
- cxf(3.1.1) 异常Caused by: java.io.FileNotFoundException: class path resource [META-INF/cxf/cxf-extension-soap.xml]
- debian 8 和centos 配置java 环境变量的正确姿态
- DB2 UDB DBA 核对清单
- JSP如何在servlet将一个数据模型对象传递给jsp页面
- Bootstrap plugin编写
- DevExpress licenses.licx 的解决方法 z
- bzoj 1602 [Usaco2008 Oct]牧场行走(LCA模板)
- Nginx 配置指令的执行顺序(三)
- relative 和 absolute 定位关系
- Java-IO之BufferedInputStream(缓冲输入流)
- 洛谷P4640 王之财宝 [BJWC2008] 数论
- ajax上传下载自定义圆形滚动条
- JetBrains PyCharm 专业版激活
- deb 和 rpm 后缀文件 区别和安装
- Swift 类
- MVC LinqToSql Json DbComparisonExpression 需要具有可比较类型的参数。
- PSP软件开发过程