LTPMSEQ spoj – Tìm xâu

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

1. Đề bài LTPMSEQ spoj

Sau khi đã giải được PTQMSEQ, PM bắt leaxtanh vượt qua thử thách thứ 2 là chứng tỏ tình cảm của mình. Leaxtanh viết ra trên giấy n xâu với những dòng chữ tình cảm.

Sau khi viết xong, với con mắt tinh đời, PM hỏi leaxtanh : có duy nhất 1 xâu xuất hiện lẻ lần. Nếu tìm được thì sẽ đi chơi.

Bạn hãy giúp leaxtanh nhé. 😀

Input

Dòng đầu tiên chứa số n( n<=10^5)

N dòng sau là các xâu st ( length(st) <=15);

Output

1 dòng duy nhất chứa xâu cần tìm.

Nếu không tìm được in ra -1;
Input:
9
Mai
Yeu
Lam
Son
Toi
Toi
Lam
Son
Yeu

Output:
Mai

2. Hướng dẫn LTPMSEQ spoj

Bài này dùng Bitmask bằng phép tính xor. tất nhiên không thể xor chuỗi vs chuỗi rồi 😀 nên bạn sẽ xor theo mã ASCII của nó.

ở đây tân dụng tính chất a xor a = 0 và 0 xor a = a. 1 chữ cái xuất hiện chẵn lần thì khi xor hết lại sẽ được 0, xuất hiện lẻ lần thì sẽ được chính nó. tạo 1 mảng s[15], mỗi khi đọc 1 xâu st, gán lại s[i] = s[i] xor st[i]. khi đọc đủ n xâu thì mảng s còn lại chính là kq.

Ngoài ra bài này còn có thể duyệt, dùng Hash + xor, sort,… cũng làm dc…

3. code tham khảo LTPMSEQ spoj

var
	n, i, j: longint;
	s: array [1..15] of longint;
	st: string;
begin
	readln(n);
	fillchar(s,sizeof(s),0);
	for i := 1 to n do
	begin
		readln(st);
		for j := 1 to length(st) do
			s[j] := s[j] xor ord(st[j]);
	end;

	for i := 1 to 15 do
	begin
		if (s[i] = 0) then exit;
		write(chr(s[i]));
	end;
end.

=================

code tham khảo cho ý tưởng khác (duyệt):

const   fi='';
var
        f:text;
        A:array[1..100000] of string[16];
        b:array[1..100000] of byte;
        n,dem:longint;
        i:longint;
        tam:string;

procedure tim;
var     i:longint;
begin
        for i:=1 to dem do
                if tam = a[i] then
                        begin
                                b[i]:=2;
                                exit;
                        end;
        inc(dem);
        a[dem]:=tam;
        b[dem]:=1;

end;

begin
        assign(f,fi); reset(f);
        readln(f,n);
        readln(f,a[1]);
        b[1]:=1;
        dem:=1;
        for i:=2 to n do
                begin
                        readln(f,tam);
                        tim;
                end;
        close(f);

        for i:=1 to dem do
                if b[i]=1 then
                        begin
                                writeln(a[i]);
                                exit;
                        end;
        writeln(-1);
end.