 |
 |
 |
Скачать программы Все программы автора
ЗАДАЧА "ШИФР"
Дана символьная строка S длины N (0 £ N £ 100) и словарь, который содержит M слов (0 £ M £ 100), длина каждого из которых не превышает N. Строка и слова состоят из символов a, b, …, z.
Задание
Напишите программу CIPHER, которая определяет наименьшее количество символов, которое необходимо вычеркнуть из заданной строки S, чтобы результирующую строку можно было представить как последовательность слов словаря. Количество использований каждого слова не ограничивается. Считается, что пустую строку можно представить с помощью слов любого словаря.
Строка в примере после вычеркивания лишних букв f и t примет вид abachdsya (было сделано два вычеркивания: abafchtdsya), и может быть представлена как последвательность следующих слов: a, bach, dsy, a.
Входные данные
В первой строке входного файла CIPHER.DAT находится два целых числа N и M, оразделенных пробелом. Во второй строке находится символьная строка S. В каждой из следующих M строк находится слово словаря.
Пример входного файла
11 5
abafchtdsya
aba
a
bach
dsy
zero
Выходные данные
В единственной строке выходного файла CIPHER.SOL должно находиться натуральное число – минимальное количество вычеркиваний, после которых зашифрованная строка может быть представлена в виде последовательности слов словаря.
Пример выходного файла 2
program Cipher;
var
fr,fw:text;
n,m:integer;
s,w:string;
ma:array[1..101,1..101] of integer;
var
wp:array[1..101] of integer;
procedure prepare;
var i,j,wl:integer;
si:char;
begin
FillChar(wp,sizeof(wp),0);
wl:=length(w);
if wl>1 then
begin
for i:=1 to n do
begin
si:=s[i];
if (wp[wl]>0)and(w[wl]=si) then
begin
if (ma[wp[wl],i+1]=-1)or(ma[wp[wl],i+1]>wl-wp[wl]-i-1) then
ma[wp[wl],i+1]:=i+1-wp[wl]-wl;
{ ma[i+1,wp[wl]]:=i+1-wp[wl]-wl;}
end;
for j:=wl-1 downto 2 do
if (wp[j]>0)and(w[j]=si) then
begin
wp[j+1]:=wp[j];
wp[j]:=0;
end;
if w[1]=si then wp[2]:=i;
end;
end else
begin
for i:=1 to n do
if s[i]=w[1] then
begin
ma[i,i+1]:=0;
{ ma[i+1,i]:=0;}
end;
end;
end;
var d,u:array[1..101] of integer;
procedure find_way(start:integer);
var i,j:integer;
dmin,darg:integer;
begin
for i:=start+1 to n+1 do d[i]:=102;
d[start]:=0;
fillChar(u,sizeof(u),0);
while true do
begin
dmin:=102;
darg:=n+1;
for j:=start to n+1 do
if (u[j]=0)and(dmin>d[j]) then
begin
dmin:=d[j];
darg:=j;
end;
if darg=n+1 then break;
u[darg]:=1;
for j:=start+1 to n+1 do
if (u[j]=0)and
(ma[darg,j]>-1)and
(d[darg]+ma[darg,j]<d[j]) then
d[j]:=d[darg]+ma[darg,j];
end;
end;
procedure Make;
var i:integer;
res:integer;
begin
find_way(1);
res:=d[n+1];
{ for i:=2 to n do
begin
if i>=res then break;
find_way(i);
if d[n+1]+i-1<res then res:=d[n+1]+i-1;
end;}
writeln(fw,res);
end;
var
i:integer;
begin
assign(fr,'cipher.dat');
reset(fr);
assign(fw,'cipher.sol');
rewrite(fw);
readln(fr,n,m);
readln(fr,s);
FillChar(ma, sizeof(ma), 255);
for i:=1 to n do
begin
ma[i,i+1]:=1;
{ ma[i+1,i]:=1;}
end;
for i:=1 to m do
begin
readln(fr,w);
prepare;
end;
Make;
close(fr);
close(fw);
end.
|
|
|
