中科新闻网全境封锁挑战难度单刷:单词的划分(word.pas)
来源：百度文库 编辑：中科新闻网 时间：2024/04/20 19:49:30
[问题描述]
有一个很长的由小写字母组成字符串。为了便于对这个字符串进行分析，需要将它划分成若干个部分，每个部分称为一个单词。出于减少分析量的目的，我们希望划分出的单词数越少越好。你来完成这一划分工作的。
应该加上一个前提题目中提供的字符串肯定能被划分，否则输出增加判断语句。
[输入文件]
从文本文件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，另外注意，单词列表中的每个单词都可以重复使用多次，也可以不用)
紧急 完成后 + 10分
有一个很长的由小写字母组成字符串。为了便于对这个字符串进行分析，需要将它划分成若干个部分，每个部分称为一个单词。出于减少分析量的目的，我们希望划分出的单词数越少越好。你来完成这一划分工作的。
应该加上一个前提题目中提供的字符串肯定能被划分，否则输出增加判断语句。
[输入文件]
从文本文件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，另外注意，单词列表中的每个单词都可以重复使用多次，也可以不用)
紧急 完成后 + 10分
program wdhf;
var a:array [0..101] of string;
f:array [0..101] of longint;
s:string;
n,i,j,ls:longint;
begin
readln(s);
readln(n);
for i:=1 to n do
readln(a[i]);
ls:=length(s);
for i:=1 to ls do
f[i]:=maxint; {初始化每个状态的最优拆分次数}
for i:=1 to ls do
{枚举每个节点}
begin
for j:=1 to n do
{枚举每个单词}
if pos(a[j],copy(s,i,ls-i+1))=1 then
{如果可以拆分出来}
if f[i+length(a[j])-1]>f[i-1]+1
then {判断当前状态和曾经状态那个更优}
f[i+length(a[j])-1]:=f[i-1]+1; {替换当前状态}
end;
writeln(f[ls]);
end.