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 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:

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

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.