Scribd
Unggah
4 tayangan3 halaman

Naive String Matching

Dokumen ini menjelaskan algoritma naïve string matching yang mencakup langkah-langkah untuk mencocokkan pola dalam teks. Proses dimulai dengan membandingkan karakter dari teks dan pola, dan jika tidak ada kecocokan, pola digeser satu karakter ke kanan. Contoh diberikan dengan input tertentu yang menunjukkan bahwa kecocokan ditemukan pada pergeseran ke-4.

Diunggah oleh

Muhammad Mahbub
Hak Cipta
© All Rights Reserved
Kami menangani hak cipta konten dengan serius. Jika Anda merasa konten ini milik Anda, ajukan klaim di sini.
Format Tersedia
Unduh sebagai DOCX, PDF, TXT atau baca online di Scribd
4 tayangan3 halaman

Naive String Matching

Dokumen ini menjelaskan algoritma naïve string matching yang mencakup langkah-langkah untuk mencocokkan pola dalam teks. Proses dimulai dengan membandingkan karakter dari teks dan pola, dan jika tidak ada kecocokan, pola digeser satu karakter ke kanan. Contoh diberikan dengan input tertentu yang menunjukkan bahwa kecocokan ditemukan pada pergeseran ke-4.

Diunggah oleh

Muhammad Mahbub
Hak Cipta
© All Rights Reserved
Kami menangani hak cipta konten dengan serius. Jika Anda merasa konten ini milik Anda, ajukan klaim di sini.
Format Tersedia
Unduh sebagai DOCX, PDF, TXT atau baca online di Scribd

String Matching - Naive String Matching

Algoritma naïve string matching informal diberikan sebagai berikut:


langkah 1: Baca teks T dan pola P
langkah 2: Sejajarkan pola P dengan teks T, dan pindah dari kiri ke kanan
langkah 3: Ulangi langkah-langkah berikut sampai seluruh pola ditemukan atau akhir teks T
ditemukan
3a: Bandingkan karakter pertama teks T dan pola P. Jika ada kecocokan, maka
pindah untuk membandingkan karakter kedua, dan seterusnya. Jika semua karakter
P cocok dengan karakter T, laporkan sukses dan keluar; jika tidak, lanjutkan ke
Langkah 4
3b: Pindahkan pola ke bawah teks dengan satu karakter (atau dengan shift) dan
tambahkan nomor shift; pergi ke Langkah 3
langkah 4: Jika pola P tidak ada di Langkah 3 dan 4, laporkan kegagalan dan akhiri.

Contoh:
Input:
T [] = “ADSFKBVCRDTP”
P [] = “KBVC”
Length [T] = 12
Length [P] = 4
Shift start from 0
S=0

A
D S F K B V C R D T P

K B V C

S=1

A D S F K B V C R D T P
K B V C

S=2

A D S F K B V C R D T P

K B V C

S=3

A D S F K B V C R D T P

K B V C

S=4

A D S F K B V C R D T P

K B V C

S=4

A D S F K B V C R D T P

K B V C

S=4

A D S F K B V C R D T P
K B V C

S=4

A D S F K B V C R D T P

K B V C
Output:
Match found at shift 4

Anda mungkin juga menyukai