NKH spoj – Tách Từ

Nguồn đề bài: http://vn.spoj.com/problems/NKH/

1. Đề bài NKH spoj

Hệ điều hành XP cho phép điều khiển cùng lúc hai bàn phím. Hai anh em Tuấn và Nam vừa được thưởng một máy tính mới nên rất muốn thử tính năng này của XP. Tuấn và Nam, mỗi người dùng một bàn phím và đồng thời gõ vào một từ đang nghĩ trong đầu tương ứng là S1 và S2. Do gõ đồng thời và tốc độ gõ khác nhau nên kết quả là trên màn hình hiện ra một chuỗi ký tự S là kết hợp của các ký tự trong S1 và S2. Các ký tự này đan xen nhau theo một trình tự nào đó khiến Tuấn và Nam không còn nhận ra ký tự nào do mình đã gõ.

Yêu cầu

• Hãy giúp Tuấn và Nam xác định những ký tự nào có thể là của mình theo nghĩa nếu tách những ký tự đó ra và ghép lại theo đúng thứ tự thì ta nhận được đúng từ mà Tuấn và Nam đã gõ.

Dữ Liệu

• Dữ liệu vào gồm 3 dòng, trong đó:
• Dòng đầu tiên chứa từ S1 do Tuấn đã gõ. Dòng thứ hai chứa từ S2 do Nam đã gõ.
• Dòng cuối cùng chứa chuỗi S. S1 và S2 chỉ chứa các chữ cái latin (a, A, b, B.. ) và số lượng ký tự trong mỗi chuỗi không vượt quá 100.

Kết Quả

• Kết quả ghi ra chỉ có một dòng duy nhất chứa chuỗi ký tự có chiều dài bằng chiều dài chuỗi S, trong đó ký tự thứ I sẽ bằng ký tự ′1′ nếu ký tự tương ứng S[I] do Tuấn gõ và bằng ′2′ nếu S[I] do Nam gõ.
• Trong trường hợp có nhiều hơn một kết quả thì in ra dãy có thứ tự từ điển bé nhất.

Ví Dụ

Input:
papa
mama
mpapamaa
Output:
21112212

2. Hướng dẫn giải NKH spoj – Tách Từ

– Xây dựng thủ tục đệ quy try(i,kt1,kt2) với ý nghĩa tìm kết quả kí tự thứ i của xâu S khi chọn kí tự s1[kt1] hoặc s2[kt2] để ghép vào vị trí i đó.

3. Code tham khảo NKH spoj – Tách Từ

const   fi='';
        nmax=200;
type    data=longint;
var
        f:text;
        s1,s2,s3:string;
        n,m:data;
        tr:array[0..nmax+1] of data;

procedure docfile;
var     i,j:data;
begin
        assign(f,fi); reset(f);
        readln(f,s1); n:=length(s1);
        readln(f,s2); m:=length(s2);
        readln(f,s3);
        close(f);
end;

procedure try(i,kt1,kt2:data); // sinh ki tu thu i
var     j:data;
begin
        if i>m+n then
                begin
                        for j:=1 to m+n do
                                write(tr[j]);
                        halt;
                end
        else
                begin
                        if s3[i]=s1[kt1] then
                                begin
                                        tr[i]:=1;
                                        try(i+1,kt1+1,kt2);
                                end;
                        if s3[i]=s2[kt2] then
                                begin
                                        tr[i]:=2;
                                        try(i+1,kt1,kt2+1);
                                end;
                end;
end;

begin
        docfile;
        try(1,1,1);
end.