tyvj1102 单词的划分

描述

有一个很长的由小写字母组成字符串。为了便于对这个字符串进行分析，需要将它划分成若干个部分，每个部分称为一个单词。出于减少分析量的目的，我们希望划分出的单词数越少越好。你就是来完成这一划分工作的。

输入格式

第一行，一个字符串。（字符串的长度不超过100）
第二行一个整数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 = 31,Sed = 131,mod = 70177,Mod = 92311; int n,m,dp[205]; string a[205],s; vector<int> h[mod]; int main(){cin>>s>>n;for(int i = 1;i <= n;i++){cin>>a[i];int hash = 0,Hash = 0;for(int j = 0;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 = 1;i <= m;i++) dp[i] = 999;for(int i = 1;i <= m;i++){for(int j = i;j >= 1;j--){int hash = 0,Hash = 0;for(int k = j - 1;k <= i - 1;k++){hash = (hash * sed + s[k]) % mod;Hash = (Hash * Sed + s[k]) % Mod;}bool ok = false;for(int k = 0;k < h[hash].size();k++){if(h[hash][k] == Hash){ok = true;break;}}if(ok) dp[i] = min(dp[i],dp[j-1] + 1);}}cout<<dp[m];return 0; }

 

转载于:https://www.cnblogs.com/hyfer/p/5791414.html

总结

以上是生活随笔为你收集整理的tyvj1102 单词的划分的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。