MORSEDEC spoj – Morse decoding
Nguồn đề bài: http://vn.spoj.com/problems/MORSEDEC/ 1. Đề bài MORSEDEC spoj Hiện nay, khi công nghệ thông tin phát triển, con người thường trao đổi với nhau bằng điện thoại, fax hay email. Hãy quay ngược thời gian lại 100 năm, khi đó con người không có điện thoại hay fax, lại ...
Nguồn đề bài: http://vn.spoj.com/problems/MORSEDEC/
1. Đề bài MORSEDEC spoj
Hiện nay, khi công nghệ thông tin phát triển, con người thường trao đổi với nhau bằng điện thoại, fax hay email. Hãy quay ngược thời gian lại 100 năm, khi đó con người không có điện thoại hay fax, lại càng chẳng có email, người ta phải liện lạc với nhau bằng mật mã MORSE. Đây là loại mật mã mà các kí tự chỉ được mã hóa bằng 2 kí hiệu “.” (tích) và “-“ (tè). Để chuyển đi một văn bản, người ta mã hóa từng chữ cái trong văn bản đó thành những dãy kí tự tích tè. Trên thế giới đã quy định một quy tắc mã hóa chuẩn như sau:
| A | .- | B | -… | C | -.-. |
D | -.. | E | . | F | ..-. |
G | –. | H | …. | I | .. |
J | .— | K | -.- | L | .-.. |
M | — | N | -. | O | — |
P | .–. | Q | –.- | R | .-. |
S | … | T | – | U | ..- |
V | …- | W | .– | X | -..- |
Y | -.– | Z | –.. |
Hạn chế của cách mã hóa này là một dãy mã hóa có thể có nhiều cách giải mã. Ví dụ dãy -.-..– có thể được hiểu là CAT hay NXT đều đúng. Rõ ràng là trong trường hợp bình thường, chúng ta sẽ phải hiểu là CAT vì NXT không có nghĩa. Tuy vậy một dãy mã hóa vẫn có thể có nhiều cách giải mã có nghĩa. Bạn có trong tay một dãy đã mã hóa và một danh sách các từ có nghĩa, bạn hãy tính xem có bao nhiêu cách giải mã có nghĩa.
(Một cách giải có nghĩa là một cách chia đoạn code ban đầu thành các đoạn con liên tiếp sao cho mỗi đoạn là một từ có nghĩa)
Input
Dòng thứ nhất ghi xâu đã mã hóa gồm không quá 10000 kí tự tích tè. Dòng thứ hai ghi số N là số các từ có nghĩa (N ≤ 1000). Trong N dòng tiếp theo, mỗi dòng ghi một từ có nghĩa. Các từ là các xâu không rỗng gồm không quá 10 kí tự trong khoảng “A” đến “Z”.
Output
Gồm một dòng duy nhất ghi số P là phần dư số cách giải mã có nghĩa khi chia cho 1 triệu (mod 1 000 000).
Example
Input:
.—.–.-.-.-.—…-.—.
6
AT
TACK
TICK
ATTACK
DAWN
DUSK
Output:
2
2. Gợi ý MORSEDEC spoj
– Dùng thuật toán Hash + QHĐ
– Xây dựng hàm QHĐ gọi Fx[i] là số lượng từ có nghĩa liên tiếp nhau và kết thúc tại vị trí i.
res = Fx[length(S)]; với S là xâu kí tự tích tè.
3. Code tham khảo MORSEDEC spoj
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 | const fi='; base=1000000007; type data=longint; var f:text; S,B:ansistring; n:data; A:string; Hash,pow,hashb,LengB:array[0..10001] of int64; res:int64; Fx:array[0..10001] of data; Function kt (C : Char) : String; Begin if C='A' then exit('.-'); if C='B' then exit('-...'); if C='C' then exit('-.-.'); if C='D' then exit('-..'); if C='E' then exit('.'); if C='F' then exit('..-.'); if C='G' then exit('--.'); if C='H' then exit('....'); if C='I' then exit('..'); if C='J' then exit('.---'); if C='K' then exit('-.-'); if C='L' then exit('.-..'); if C='M' then exit('--'); if C='N' then exit('-.'); if C='O' then exit('---'); if C='P' then exit('.--.'); if C='Q' then exit('--.-'); if C='R' then exit('.-.'); if C='S' then exit('...'); if C='T' then exit('-'); if C='U' then exit('..-'); if C='V' then exit('...-'); if C='W' then exit('.--'); if C='X' then exit('-..-'); if C='Y' then exit('-.--'); if C='Z' then exit('--..'); End; procedure power; var i,j:data; begin pow[0]:=1; for i:=1 to length(s) do pow[i]:=(pow[i-1]*2) mod base; end; function get(i,j:data):int64; begin get:=(hash[j]-hash[i-1]*pow[j-i+1] + base*base) mod base; end; Function DC (C : Char) : Int64; Begin if C='.' then exit(0) else exit(1); End; procedure taohash; var i,j:data; begin hash[0]:=0; for i:=1 to length(s) do hash[i]:=(hash[i-1]*2 + dc(s[i])) mod base; end; function max(a,b:data):data; begin if a>b then exit(a); exit(b); end; procedure init(test:data); var i,j:data; hash:int64; begin b:='; for i:=1 to length(a) do b:=b+kt(a[i]); LengB[test]:=length(b); Hash:=0; for i:=1 to length(b) do hash:=(hash*2+dc(b[i])) mod base; hashB[test]:=hash; end; procedure docfile; var i,j:data; begin assign(f,fi); reset(f); readln(f,s); power; taohash; fillchar(fx,sizeof(fx),0); Fx[0]:=1; readln(f,n); res:=0; for i:=1 to n do begin readln(f,a); init(i); end; close(f); end; procedure tinh; var i,j:data; begin for i:=1 to length(s) do begin for j:=1 to n do if lengB[j]<=i then if get(i-lengB[j]+1,i)=hashB[j] then fx[i]:=(Fx[i]+fx[i-lengB[j]]) mod 1000000; end; end; begin docfile; tinh; writeln(Fx[length(s)]); end. |
