单词的划分

admin

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

输入格式
    从文本文件word.in中读入数据。
    第一行，一个字符串。（字符串的长度不超过100）
    第二行一个整数n，表示单词的个数。（n<=100）
    第3~n+2行，每行列出一个单词。

输出格式
    一个整数，表示字符串可以被划分成的最少的单词数。

样例输入
realityour
5
real
reality
it
your
our

样例输出
2
（原字符串可拆成real+it+your或reality+our，由于reality+our仅为两个部分，因此最优解为2，另外注意，单词列表中的每个单词都可以重复使用多次，也可以不用）

YTC

1. #include<iostream>
   
2. #include<cstdio>
   
3. using namespace std;
   
4. string ss;
   
5. string s[101];
   
6. int n;
   
7. int f[105];
   
8. bool judge(int l,string s)
   
9. {
   
10.     if(ss.size()-l<s.size()) return false;
    
11.     for(int i=l;i<l+s.size();i++)
    
12.         if(ss[i]!=s[i-l]) return false;
    
13.     return true;
    
14. }
    
15. int dfs(int p)
    
16. {
    
17.     if(f[p]) return f[p];
    
18.     if(p>=ss.size()) return 0;
    
19.     int ans=999999;
    
20.     for(int i=1;i<=n;i++)
    
21.         if(judge(p,s[i])) ans=min(dfs(p+s[i].size())+1,ans);
    
22.     return f[p]=ans;
    
23. }
    
24. int main()
    
25. {
    
26.     freopen("word.in","r",stdin);
    
27.     freopen("word.out","w",stdout);
    
28.     cin>>ss;
    
29.     cin>>n;
    
30.     for(int i=1;i<=n;i++) cin>>s[i];
    
31.     dfs(0);
    
32.     cout<<f[0];
    
33.     return 0;
    
34. }
    

复制代码