Bahas Soal Terbaru - Strings... Strings Everywhere... | TOKI Learning Center

Link Soal : http://tokilearning.org/problem/1495

sebenarnya cukup tegang dengan soal ini :D
but it's not a reason.

Ok, langsung saja



Ingat :
Pada semua kasus, total banyak karakter pada N buah string (tidak termasuk s) yang ada pada masukan tidak melebihi 200 000. Selain itu, masing-masing dari N buah string itu panjangnya tidak melebihi panjang s.

• Subtask 1 (30 poin): panjang s melebihi nol tapi tidak melebihi 1000. 1 <= N <= 1000.
• Subtask 2 (70 poin): panjang s melebihi nol tapi tidak melebihi 100 000. 1 <= N <= 100 000.

Format Masukan

Baris pertama masukan berisi sebuah string s sesuai pada deskripsi soal. Kemudian, baris kedua berisi sebuah bilangan bulat N. Pada N baris berikutnya, masing-masing berisi sebuah string a[i].

Format Keluaran

Sebuah baris berisi sebuah bilangan bulat yang merupakan banyaknya string dari N buah string yang merupakan subsequence dari s.

apa itu subsequence???
subsequence itu maksudnya apakah string tersebut merupakan bagian dari string sebelumnya
misalnya
string S=asbcdefghijklmnopqrstuvw
string A=defghij
string B=mno
string C=ghj
string D=klmo

maka A dan B termasuk subsequence dari S sedangkan C dan D tidak.


Bagaimana mendapatkan 200000 karakter sedangkan string hanya memuat 255 karakter???
Bisa,,, gunakan array of char.

Mulai Pembahasan :

Pertama siapkan sebuah kode algoritma untuk menginput karakter yang sampai sepanjang 200000 karakter itu spt ini.

    while not(EOLN) do begin

        inc(i);

        read(x[i]);

    end;

silahkan diperhatikan !
EOLN adalah sebuah fungsi yang membaca data hingga akhir baris/hingga ditemukan baris baru.


Siapkan juga pembaca subsequence yang diminta seperti ini

while (j<=N) do begin

.......


        while not(EOLN) do begin

           inc(k);

           read(y[k]);

        end;

.......
end;

silahkan diperhatikan. ! (N adalah banyak subsequence yang akan diperiksa)

Selanjut nya buat sebuah fungsi yang memeriksa apakah subsequence ada pada string yang ditentukan spt. ini

function cek(S:char;h:integer):boolean;

var

    g,b : integer;

    salah : boolean;

begin

    for g:=1 to i-1 do begin

        if S=x[g] then begin

            salah:=false;

            for b:=g to (g+h) do

                begin  

                    if not(y[b-g+1]=x[b]) then salah:=true;

                end;

                if not(salah) then begin

                    cek:=true;   

                    break;

                end;

        end;

    end;

    if salah then cek:=false;

end;

dimana pada fungsi tsb. h adalah panjang subsequence (mis pada contoh subsequence diatas panjang A=7, B=3, dst) dan S pada fungsi tsb adalah karakter pertama dari subsequence tadi (mis pada contoh subsequence diatas karakter pertama A=d, B=m)


dari pembahasan singkat diatas didapat jawaban spt. berikut ini :

var

    x,y : array[1..200000] of char;

    c,i,j,k,N : integer;

function cek(S:char;h:integer):boolean;

var

    g,b : integer;

    salah : boolean;

begin

    for g:=1 to i-1 do begin

        if S=x[g] then begin

            salah:=false;

            for b:=g to (g+h) do

                begin  

                    if not(y[b-g+1]=x[b]) then salah:=true;

                end;

                if not(salah) then begin

                    cek:=true;   

                    break;

                end;

        end;

    end;

    if salah then cek:=false;

end;

begin

c:=0;

i:=0;

j:=1;

    while not(EOLN) do begin

        inc(i);

        read(x[i]);

    end;

readln(N);

while (j<=N) do begin

        k:=0;

        while not(EOLN) do begin

           inc(k);

           read(y[k]);

        end;

    if cek(y[1],k-1) then inc(c);

    readln;

    inc(j);

end;

writeln(c);

end.

 

Sekian Pembahasan Kali ini ... See You...

TOKI GO GET GOLD