描述

有一個(gè)很長(zhǎng)的由小寫(xiě)字母組成字符串。為了便于對(duì)這個(gè)字符串進(jìn)行分析，需要將它劃分成若干個(gè)部分，每個(gè)部分稱(chēng)為一個(gè)單詞。出于減少分析量的目的，我們希望劃分出的單詞數(shù)越少越好。你就是來(lái)完成這一劃分工作的。

輸入格式

第一行，一個(gè)字符串。（字符串的長(zhǎng)度不超過(guò)100）
第二行一個(gè)整數(shù)n，表示單詞的個(gè)數(shù)。（n<=100）
第3~n+2行，每行列出一個(gè)單詞。

輸出格式

一個(gè)整數(shù)，表示字符串可以被劃分成的最少的單詞數(shù)。

測(cè)試樣例1

輸入

realityour?
5?
real?
reality?
it?
your?
our

輸出

2

備注

（原字符串可拆成real+it+your或reality+our，由于reality+our僅為兩個(gè)部分，因此最優(yōu)解為2，另外注意，單詞列表中的每個(gè)單詞都可以重復(fù)使用多次，也可以不用） #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; }

?

轉(zhuǎn)載于:https://www.cnblogs.com/hyfer/p/5791414.html

總結(jié)

以上是生活随笔為你收集整理的tyvj1102 单词的划分的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。