E.SSN : 2721-1800 (Online)
https://journal.cattleyadf.org/index.php/jatilima/index
Implementasi Algoritma Greedy dan String Matching Penukaran Uang Menjadi Koin, Pencarian Pola dalam Teks yang Berisi Nama ”Indomaret” – Muhammad Arif Afandy  et.al

## Implementasi Algoritma Greedy dan String Matching Penukaran Uang Menjadi Koin, Pencarian Pola dalam Teks yang Berisi Nama ” Indomaret ”
Muhammad Arif Afandy 1 , Septio Praja 2 , Tulus Andriansah 3
Teknik Informatika, Universitas Palangkaraya, Jl. Yos Sudarso, Kota Palangka Raya, Indonesia
Article Info ABSTRACT Keywords: Algoritma String Maching Algoritma Greedy Penukaran Uang Koin Penelitian ini bertujuan untuk mengimplementasikan algoritma greedy dalam penukaran uang Rupiah menjadi koin 100 Rupiah dan algoritma pencarian  pola  dalam  teks  yang  berisi  nama  "Indomaret"  di  berbagai kota  di  Indonesia  menggunakan  algoritma  string  matching.
Implementasi  algoritma  greedy  dilakukan  untuk  memberikan  solusi efisien  dalam  menyelesaikan  permasalahan  penukaran  uang  menjadi koin 100 Rupiah dengan meminimalkan jumlah koin yang diperlukan. Algoritma  pencarian  pola  dalam  teks  menggunakan  string  matching digunakan untuk mencari keberadaan nama "Indomaret" di teks yang berisi daftar kota-kota di Indonesia. Implementasi ini dapat membantu dalam identifikasi lokasi dari gerai Indomaret di berbagai kota, sehingga memudahkan  pengguna  untuk  menemukan  gerai  tersebut.  Hasil  dari penelitian  ini  dapat  digunakan  sebagai  dasar  untuk  pengembangan sistem  yang  lebih  kompleks  dalam  manajemen  uang  dan  informasi lokasi gerai. This  is  an  open  access  article under the CC BY-NC license Corresponding Author: Muhammad Arif Afandy Universitas Palangkaraya Jl. Yos Sudarso, Palangka, Kec. Jekan Raya, Kota Palangka Raya,
Kalimantan Tengah 74874 afandyarif417@gmail.com

## INTRODUCTION
Algoritma  merupakan  langkah-langkah  sistematis  untuk  menyelesaikan  masalah dalam komputasi dan matematika. Dalam banyak kasus, terdapat beragam jenis algoritma yang  dapat  digunakan  untuk  menyelesaikan  suatu  masalah  tertentu.  Dua  di  antaranya adalah  algoritma  Greedy  dan  algoritma  pencocokan  string  (string  matching).  Dalam pendahuluan  ini,  penulis  akan  menjelaskan  sejarah  dan  memberikan  gambaran  singkat tentang kedua algoritma tersebut serta relevansinya dalam berbagai bidang.
Algoritma  Greedy,  atau  sering  disebut  juga  dengan  pendekatan  "serakah",  adalah salah satu paradigma dalam desain algoritma yang memilih solusi yang terlihat terbaik pada setiap tahap dengan harapan bahwa pemilihan tersebut akan mengarah pada solusi global yang optimal. Meskipun Greedy cenderung menghasilkan solusi yang dekat dengan optimal dalam banyak kasus, namun tidak selalu menjamin solusi yang benar-benar optimal dalam hal masalah yang kompleks (Zhang et al., 2000).

## Implementasi Algoritma Greedy dan String Matching Penukaran Uang Menjadi Koin,
Pencarian Pola dalam Teks yang Berisi Nama ”Indomaret” – Muhammad Arif Afandy  et.al
Sejarah  algoritma  Greedy  dapat  ditelusuri  kembali  ke  awal  perkembangan  teori algoritma. Salah satu contoh awal penerapan Greedy adalah dalam algoritma Dijkstra untuk mencari jalur terpendek dalam graf. Algoritma ini diusulkan oleh Edsger W (Ruiz & Stützle, 2007). Dijkstra pada tahun 1956 dan menjadi salah satu fondasi dalam algoritma Greedy modern. Sejak saat itu, Greedy telah banyak diterapkan dalam berbagai konteks, termasuk optimasi kombinatorial, jaringan, dan kecerdasan buatan (Vince, 2002).
Prinsip  dasar  dari  algoritma  Greedy  adalah  membuat  keputusan  lokal  yang  terlihat terbaik  pada  setiap  langkah  dengan  harapan  bahwa  solusi  yang  dihasilkan  secara keseluruhan  juga  akan  optimal.  Langkah-langkah  dalam  algoritma  Greedy  tidak mempertimbangkan konsekuensi jangka panjang dari keputusan tersebut, melainkan hanya memperhatikan keadaan saat ini (Septiana et al., 2022).
Misalnya, dalam masalah penukaran uang, algoritma Greedy akan memilih pecahan uang terbesar yang dapat ditukarkan untuk setiap permintaan penukaran. Dengan demikian, algoritma Greedy akan berulang kali memilih pecahan terbesar hingga jumlah yang tersisa menjadi  nol  atau  mencapai  nilai  yang  diinginkan.  Namun,  perlu  dicatat  bahwa  algoritma Greedy mungkin tidak selalu menghasilkan solusi optimal, terutama jika ada kondisi khusus yang tidak memenuhi prinsip Greedy (Darnila et al., 2019).
Algoritma pencocokan string adalah teknik yang digunakan untuk mencari kemunculan suatu pola ( pattern ) dalam teks ( text ). Tujuan dari algoritma ini adalah untuk menemukan posisi  kemunculan  semua  kemungkinan  pola  dalam  teks  dengan  efisien.  Algoritma pencocokan string telah menjadi bagian integral dari banyak aplikasi dalam pemrosesan teks, seperti  pencarian  teks,  pengindeksan  teks,  dan  analisis  bioinformatika  (Anggreani  et  al., 2020).
Salah  satu  algoritma  pencocokan  string  paling  terkenal  adalah  algoritma  Knuth- Morris-Pratt (KMP), yang dikembangkan oleh Donald Knuth, Vaughan Pratt, dan James H. Morris  pada  tahun  1970-an  (Commentz-Walter,  1979).  Algoritma  ini  menggunakan pendekatan yang cerdas untuk menghindari pencocokan ulang yang tidak perlu antara teks dan pola, sehingga meningkatkan efisiensi pencarian (Nizar et al., 2024).
Pada dasarnya, algoritma KMP membagi teks menjadi bagian-bagian yang lebih kecil dan mencocokkan pola dengan bagian-bagian ini secara bergantian (Charalampopoulos et al., 2020). Jika ada ketidaksesuaian antara pola dan teks, algoritma KMP akan memanfaatkan informasi pra-pencocokan untuk memutuskan bagian mana dari teks yang perlu diabaikan dalam pencarian berikutnya (Ahmad et al., 2021).
Kedua algoritma Greedy dan pencocokan string memiliki relevansi yang besar dalam berbagai  bidang,  termasuk  pemrosesan  teks,  jaringan  komputer,  kecerdasan  buatan,  dan optimasi kombinatorial. Penerapan algoritma Greedy dapat membantu dalam menyelesaikan masalah  optimasi  dengan  cepat  dan  mudah  dimengerti,  meskipun  tidak  menjamin  solusi yang  optimal.  Di  sisi  lain,  algoritma  pencocokan  string  memberikan  kemampuan  untuk mencari  pola  dalam  teks  dengan  efisien,  yang  sangat  penting  dalam  aplikasi  seperti pengindeksan teks dan analisis bioinformatika (Zhang et al., 2000), (Vince, 2002).
Dengan  pemahaman  yang  mendalam  tentang  kedua  algoritma  ini,  kita  dapat mengembangkan  solusi  yang  efisien  dan  optimal  untuk  berbagai  masalah  di  berbagai bidang. Dalam penelitian ini, kami akan menjelajahi penerapan kedua algoritma ini dalam hal penukaran uang dan pencocokan lokasi cabang minimarket, dengan harapan memberikan

## Implementasi Algoritma Greedy dan String Matching Penukaran Uang Menjadi Koin,
Pencarian Pola dalam Teks yang Berisi Nama ”Indomaret” – Muhammad Arif Afandy  et.al
kontribusi  yang  berarti  terhadap  efisiensi  operasional  dan  kenyamanan  pengguna  dalam kehidupan sehari-hari.
Dalam penelitian ini, kami akan menjelajahi penerapan kedua algoritma ini dalam hal penukaran uang dan pencocokan lokasi cabang minimarket, dengan harapan memberikan kontribusi  yang  berarti  terhadap  efisiensi  operasional  dan  kenyamanan  pengguna  dalam kehidupan sehari-hari.

## Systematic Literatur Review (SLR)
Systematic Literature Review (SLR) adalah sebuah metode penelitian yang sistematis untuk mengidentifikasi,  mengevaluasi,  dan  menginterpretasikan  semua  penelitian  yang  relevan yang  telah  dilakukan  dalam  suatu  bidang  pengetahuan  tertentu.  Pendekatan  ini memungkinkan  peneliti  untuk  menyusun,  menganalisis,  dan  menyimpulkan  temuan  dari berbagai sumber literatur yang ada secara objektif dan terstruktur. SLR memiliki beberapa langkah yang dapat diikuti, termasuk:
1. Identifikasi Topik Penelitian : Langkah pertama dalam SLR adalah mengidentifikasi topik atau pertanyaan penelitian yang jelas dan relevan.  Hal ini memastikan fokus yang tepat dalam mencarI literatur.
2. Pencarian Literatur : Peneliti melakukan pencarian literatur menggunakan basis data ilmiah yang terpercaya, seperti PubMed, IEEE Xplore, atau Google Scholar. Pencarian ini mencakup penggunaan kata kunci yang relevan dan pemilihan kriteria inklusi dan eksklusi yang sesuai.
3. Seleksi  Studi : Setelah pencarian literatur dilakukan, peneliti meninjau abstrak dan teks penuh dari setiap artikel untuk menentukan apakah studi tersebut memenuhi kriteria inklusi. Artikel yang relevan kemudian dipilih untuk dianalisis lebih lanjut.
4. Ekstraksi Data : Data yang relevan dari setiap artikel yang dipilih diekstraksi secara sistematis. Ini bisa berupa temuan utama, metode penelitian, dan hasil dari studi yang dilaporkan.
5. Evaluasi  Kualitas :  Kualitas  metodologi  dari  setiap  studi  yang  dimasukkan  dalam review dievaluasi. Ini memastikan bahwa temuan yang diambil dari literatur memiliki keandalan dan validitas yang tinggi.
6. Analisis  dan  Interpretasi :  Data  yang  diekstraksi  dari  literatur  dianalisis  secara menyeluruh,  baik  secara  kuantitatif  maupun  kualitatif.  Hal  ini  membantu  peneliti dalam memahami tren, pola, dan kesimpulan dari literatur yang telah ditinjau.
7. Penyusunan Laporan : Hasil dari SLR disusun dalam sebuah laporan sistematis yang mencakup gambaran menyeluruh tentang topik penelitian, temuan dari literatur, serta implikasi dan saran untuk penelitian selanjutnya.
SLR  penting  dalam  hal  penelitian  ilmiah  karena  memberikan  landasan  yang  kuat  untuk memahami  status  pengetahuan  yang  ada  dalam  suatu  bidang.  Dengan  memperoleh pemahaman  yang  komprehensif  tentang  literatur  yang  relevan,  peneliti  dapat mengidentifikasi celah pengetahuan, mengembangkan hipotesis baru, dan merancang studi penelitian yang lebih lanjut secara efektif.

## Algoritma Greedy

## Implementasi Algoritma Greedy dan String Matching Penukaran Uang Menjadi Koin,
Pencarian Pola dalam Teks yang Berisi Nama ”Indomaret” – Muhammad Arif Afandy  et.al
Algoritma  Greedy  adalah  paradigma  algoritma  yang  berfokus  pada  pengambilan keputusan pada setiap langkah berdasarkan kriteria lokal terbaik, tanpa mempertimbangkan implikasi  keputusan  pada  langkah-langkah  selanjutnya.  Dalam  hal  optimasi,  algoritma Greedy bertujuan untuk menemukan solusi yang optimal secara global dengan melakukan serangkaian keputusan lokal yang optimal pada setiap langkahnya (Roihan et al., 2022).
Konsep dasar dari algoritma Greedy adalah memilih pilihan terbaik yang tersedia pada setiap  langkah,  tanpa  mempertimbangkan  gambaran  keseluruhan  masalah.  Kriteria pemilihan  ini  didasarkan  pada  heuristik  atau  aturan  yang  telah  ditentukan  sebelumnya. Meskipun  algoritma  Greedy  tidak  menjamin  solusi  yang  optimal  untuk  setiap  masalah, namun dalam banyak kasus, algoritma ini memberikan solusi yang cukup baik dalam waktu yang efisien. Langkah-langkah Algoritma Greedy (Vince, 2002),  (Darnila et al., 2019).
1. Inisialisasi: Langkah pertama dalam algoritma Greedy adalah melakukan inisialisasi, yaitu  menentukan  nilai  awal  untuk  setiap  variabel  yang  diperlukan  dalam  proses algoritma.
2. Seleksi Langkah: Pada setiap langkah, algoritma Greedy memilih pilihan terbaik yang tersedia  berdasarkan  aturan  atau  heuristik  yang  telah  ditentukan  sebelumnya. Keputusan ini didasarkan pada evaluasi lokal dari setiap pilihan yang tersedia.
3. Evaluasi:  Setelah  langkah  dipilih,  algoritma  mengevaluasi  dampak  dari  keputusan tersebut  pada  solusi  keseluruhan.  Namun,  evaluasi  ini  hanya  mempertimbangkan kontribusi  lokal  dari  langkah  tersebut,  tanpa  memperhitungkan  dampaknya  pada langkah-langkah selanjutnya.
4. Iterasi: Proses seleksi langkah dan evaluasi dilakukan secara iteratif sampai kriteria berhenti terpenuhi. Kriteria berhenti ini dapat berupa mencapai solusi yang memenuhi syarat tertentu atau sampai tidak ada langkah lagi yang dapat diambil.
5. Penyelesaian:  Algoritma  Greedy  menghasilkan  solusi  final  ketika  iterasi  selesai. Solusi ini mungkin tidak selalu optimal, tetapi sering kali cukup baik untuk digunakan dalam banyak kasus.
Salah satu contoh penerapan algoritma Greedy adalah pada masalah penjadwalan kegiatan (scheduling problem). Misalkan terdapat sejumlah kegiatan dengan waktu mulai dan waktu selesai  yang  berbeda-beda,  dan  tujuan adalah menemukan urutan penjadwalan  kegiatan yang  memungkinkan  untuk  menyelesaikan  sebanyak  mungkin  kegiatan  tanpa  tumpang tindih.  Dalam  hal  ini,  algoritma  Greedy  dapat  digunakan  dengan  memilih  kegiatan  yang memiliki waktu selesai paling awal pada setiap langkahnya (Vince, 2002).
Kelebihan dari penggunaan algoritma Greedy adalah sebagai berikut:
a. Algoritma  Greedy  cenderung  lebih  sederhana  dan  mudah  dimengerti  dibandingkan dengan beberapa teknik optimasi yang lebih kompleks.
b. Algoritma  Greedy  sering  kali  memiliki  kompleksitas  waktu  yang  rendah,  sehingga dapat diimplementasikan secara efisien untuk masalah-masalah skala besar.

## Implementasi Algoritma Greedy dan String Matching Penukaran Uang Menjadi Koin,
Pencarian Pola dalam Teks yang Berisi Nama ”Indomaret” – Muhammad Arif Afandy  et.al
c. Solusi Cepat: Algoritma Greedy biasanya menghasilkan solusi dengan cepat karena mengambil keputusan berdasarkan aturan lokal.
Keterbatasan algoritma Greedy adalah sebagai berikut:
a. Algoritma  Greedy  tidak  menjamin  solusi  optimal  untuk  setiap  masalah,  sehingga dapat menghasilkan solusi yang suboptimal dalam beberapa kasus.
b. Kinerja  algoritma  Greedy  sangat  dipengaruhi  oleh  pemilihan  aturan  atau  heuristik yang digunakan untuk memilih langkah terbaik pada setiap langkahnya.
c. Algoritma  Greedy  cenderung  kurang cocok untuk masalah-masalah  yang  memiliki struktur yang kompleks atau terkait dengan ketergantungan antar langkah.

## String Matching
Pencocokan  string  adalah  proses  mencari  kemunculan  suatu  pola  ( pattern )  dalam sebuah  teks.  Teknik  ini  merupakan  bagian  penting  dalam  berbagai  aplikasi  komputasi, termasuk pengolahan bahasa alami, analisis teks, dan pengenalan pola dalam data biologis. Dalam hal algoritma, terdapat berbagai pendekatan untuk mencocokkan pola dalam teks, mulai dari metode pencocokan string naif hingga algoritma yang lebih efisien seperti Knuth- Morris-Pratt (KMP) dan algoritma Boyer-Moore.

## Algoritma Knuth Morris Pratt
Algoritma Knuth-Morris-Pratt (KMP) adalah sebuah algoritma pencocokan string yang efisien untuk mencari kemunculan sebuah pola (pattern) dalam sebuah teks. Dibandingkan dengan metode pencocokan string naif, KMP memanfaatkan informasi praproses dari pola untuk meminimalkan jumlah karakter yang harus dibandingkan (Ruiz & Stützle, 2007).
Langkah-langkah Algoritma Knuth-Morris-Pratt (KMP) untuk pencocokan pola dalam sebuah teks adalah sebagai berikut (Anggreani et al., 2020):
1. Pra-pemrosesan  Pola :  Langkah  pertama  algoritma  KMP  adalah  membuat  tabel lompatan  (failure  function)  yang  menyimpan  informasi  tentang  kemungkinan ketidakcocokan antara pola dan teks. Tabel ini digunakan untuk menentukan langkah berikutnya ketika terjadi ketidakcocokan selama pencocokan.
2. Pencocokan Teks dan Pola : Algoritma KMP memulai pencocokan pada posisi awal teks  dan  pola.  Ketika  terjadi  ketidakcocokan  pada  posisi  tertentu,  algoritma menggunakan tabel lompatan untuk menentukan jumlah karakter yang harus dilewati sebelum mencoba mencocokkan pola lagi.
3. Pencarian Kemunculan Pola : Algoritma KMP melanjutkan proses pencocokan sampai seluruh teks telah dijelajahi atau kemunculan pola telah ditemukan. Setiap kali pola cocok dengan segmen teks, posisi tersebut dicatat sebagai kemunculan pola.
Salah  satu  keunggulan  utama  dari  Algoritma  Knuth-Morris-Pratt  (KMP)  adalah efisiensi waktu yang tinggi dalam pencarian pola dalam sebuah teks. Dibandingkan dengan

## Implementasi Algoritma Greedy dan String Matching Penukaran Uang Menjadi Koin,
Pencarian Pola dalam Teks yang Berisi Nama ”Indomaret” – Muhammad Arif Afandy  et.al
metode brute-force yang melakukan pencocokan karakter per karakter, KMP menggunakan tabel  lompatan  yang  telah  diproses  sebelumnya  untuk  menghindari  pembacaan  ulang karakter yang sudah cocok. Hal ini menghasilkan kinerja yang lebih cepat terutama ketika pola  memiliki  kemiripan  dengan  teks  yang  luas.  Selain  itu,  keunggulan  lainnya  adalah kemampuan algoritma KMP untuk menemukan semua kemunculan pola dalam teks dengan waktu yang konstan per karakter dalam teks, tanpa terpengaruh oleh panjang pola yang dicari.  Dengan  demikian,  algoritma  KMP  menjadi  pilihan  yang  efisien  dan  andal  dalam aplikasi yang memerlukan pencarian pola dalam teks dengan cepat dan efisien.
Misalkan kita memiliki sebuah teks "ABABABCABABABCABABABC" dan kita ingin mencari kemunculan pola "ABABAC" di dalamnya menggunakan algoritma KMP. Langkah- langkahnya adalah sebagai berikut (Ilham & Mirza, 2020):
1. Pra-pemrosesan pola "ABABAC" untuk membuat tabel lompatan.
2. Pencocokan dimulai pada posisi awal teks dan pola.
3. Pada posisi keempat, terjadi ketidakcocokan pada karakter "B" dalam teks dan "C" dalam  pola.  Algoritma  menggunakan  tabel  lompatan  untuk  menentukan  langkah selanjutnya.
4. Algoritma  melompat  ke  posisi  berikutnya  dalam  teks  di  mana  karakter  "A"  cocok dengan karakter pertama dalam pola.
5. Proses pencocokan berlanjut sampai seluruh teks telah dijelajahi atau kemunculan pola telah ditemukan.
Algoritma Knuth-Morris-Pratt (KMP) adalah algoritma yang efisien dan andal untuk pencocokan  string.  Dengan  memanfaatkan  informasi  praproses  dari  pola,  KMP  mampu mencari kemunculan pola dalam teks dengan kompleksitas waktu yang rendah (Anggreani et al., 2020), (Nizar et al., 2024). Hal ini membuatnya menjadi pilihan yang populer dalam berbagai aplikasi yang membutuhkan pencocokan string yang cepat dan efisien.

## METHODS
Dalam penelitian ini, penulis akan mengevaluasi metode penelitian berdasarkan tiga kriteria utama: kelengkapan ( completeness ), optimalitas ( optimality ), dan kompleksitas waktu ( time complexity ).

## Completeness
Kelengkapan mengacu pada sejauh mana metode penelitian mencakup semua aspek yang  diperlukan  untuk  mencapai  tujuan  penelitian.  Dalam  hal  ini,  kelengkapan  akan dievaluasi  berdasarkan  sejauh  mana  metode  penelitian  mencakup  langkah-langkah  yang diperlukan  untuk  mengimplementasikan  algoritma  Greedy  dalam  penukaran  uang  di Indomaret dan algoritma pencocokan string untuk pencarian cabang Indomaret di berbagai kota  di  Indonesia.  Hal  ini  termasuk  analisis,  desain,  pengembangan  perangkat  lunak, pengujian, evaluasi, perbaikan, dan penyempurnaan (Janson et al., 2018).

## Implementasi Algoritma Greedy dan String Matching Penukaran Uang Menjadi Koin,
Pencarian Pola dalam Teks yang Berisi Nama ”Indomaret” – Muhammad Arif Afandy  et.al

## Optimality
Optimalitas mengacu pada sejauh mana metode penelitian dapat mencapai hasil yang optimal  dalam  hal  penelitian  yang  diberikan.  Dalam  hal  ini,  optimalitas  akan  dievaluasi berdasarkan efektivitas dan efisiensi algoritma yang diimplementasikan. Algoritma Greedy dalam  penukaran  uang  di  Indomaret  dan  algoritma  pencocokan  string  untuk  pencarian cabang  Indomaret  diharapkan  dapat  memberikan  solusi  yang  optimal  dalam  hal  efisiensi operasional, akurasi, dan kinerja keseluruhan .

## Time Complexity
Kompleksitas  waktu  mengacu  pada  seberapa  efisien  metode  penelitian  dalam menghabiskan waktu untuk menyelesaikan tugas yang diberikan. Dalam hal ini, kompleksitas waktu  akan  dievaluasi  berdasarkan  kompleksitas  algoritma  yang  diimplementasikan. Algoritma  Greedy  dan  algoritma  pencocokan  string  yang  digunakan  dalam  penelitian  ini diharapkan memiliki kompleksitas waktu yang rendah agar dapat memberikan kinerja yang cepat dan responsif dalam penukaran uang di Indomaret dan pencarian cabang Indomaret.

## RESULTS AND DISCUSSION

## Menggunakan Algoritma Greedy
Algoritma Greedy merupakan pendekatan yang digunakan dalam proses penukaran uang di Indomaret. Contoh implementasi algoritma Greedy dalam bahasa pemrograman C++ dapat dilihat di Gambar 1.
Gambar 1. Implementasi Algoritma Greedy Langkah-langkah yang diambil dalam algoritma tersebut adalah sebagai berikut:
1. Persiapkan  data  denominasi  uang  yang  akan  digunakan  dalam  penukaran. Denominasi uang akan diurutkan dari yang terbesar ke yang terkecil.Iterasi melalui

## Implementasi Algoritma Greedy dan String Matching Penukaran Uang Menjadi Koin,
Pencarian Pola dalam Teks yang Berisi Nama ”Indomaret” – Muhammad Arif Afandy  et.al
stok  uang  dan  mencoba  untuk  menukarkan  sebanyak  mungkin  uang  dengan  nilai pecahan yang lebih besar terlebih dahulu.
2. Lakukan  pengurutan  denominasi  uang  dari  yang  terbesar  ke  yang  terkecil.  Ini memungkinkan  algoritma  untuk  memproses  denominasi  dengan  nilai  tertinggi terlebih  dahulu.Menampilkan  hasil  penukaran  uang,  termasuk  jumlah  lembar/koin pecahan uang yang berhasil ditukarkan.
3. Inisialisasikan variabel yang diperlukan, seperti jumlah uang yang perlu diturkarkan dan jumlah koin untuk setiap dominasi.
4. Lakukan iterasi melalui setiap denominasi uang. Pada setiap iterasi, pilih sebanyak mungkin  koin  dengan  denominasi  yang  sesuai  untuk  ditukarkan  tanpa  melebihi jumlah uang yang perlu ditukarkan.
Algoritma Greedy digunakan karena pada setiap langkahnya, algoritma tersebut akan memilih  denominasi  uang  terbesar  yang  masih  memungkinkan  untuk  ditukarkan  tanpa melebihi  jumlah  uang  yang  perlu  ditukarkan.  Dengan  demikian,  algoritma  ini  dapat memberikan solusi yang optimal dalam hal minimisasi jumlah koin yang digunakan.
Proses  pengurutan  denominasi  uang  dari  yang  terbesar  ke  yang  terkecil memungkinkan  algoritma  untuk  memproses  denominasi  dengan  nilai  tertinggi  terlebih dahulu. Hal ini penting karena denominasi dengan nilai tertinggi lebih mungkin menghasilkan jumlah koin yang lebih sedikit.
Selama  iterasi,  algoritma  akan  terus  memproses  denominasi  dengan  denominasi terbesar yang masih memungkinkan tanpa melebihi jumlah uang yang perlu ditukarkan. Ini dilakukan untuk meminimalkan jumlah koin yang digunakan dalam penukaran uang.

## Menggunakan Algoritma String Matching
Algoritma String Matching digunakan dalam pencarian cabang Indomaret di berbagai kota  di  Indonesia.  Pencocokan  string  adalah  teknik  yang  penting  dalam  komputasi  untuk menemukan kemunculan sebuah pola (pattern) dalam sebuah teks.
Dalam implementasi algoritma String Matching, digunakan algoritma Knuth-Morris- Pratt  (KMP),  yang  telah  terbukti  efisien  dalam  mencocokkan  pola  dalam  teks  dengan kompleksitas waktu yang rendah. Berikut adalah implementasi pseudocode algoritma KMP string matching dengan bahasa C++:

## Implementasi Algoritma Greedy dan String Matching Penukaran Uang Menjadi Koin,
Pencarian Pola dalam Teks yang Berisi Nama ”Indomaret” – Muhammad Arif Afandy  et.al

## Gambar 2. Implementasi Algoritma String Matching
Pencarian  pola  dalam  teks  yang  berisi  nama  "Indomaret"  di  kota-kota  di  Indonesia menggunakan algoritma string matching merupakan sebuah proses yang kompleks namun penting dalam pengembangan sistem informasi terkait penelusuran lokasi gerai Indomaret. Dalam  penjelasan  ini,  akan  dibahas  secara  mendalam  mengenai  implementasi  dan pentingnya algoritma string matching dalam konteks pencarian nama "Indomaret" di teks yang berisi nama-nama kota di Indonesia.
Pencarian  pola  dalam  teks  adalah  proses  penting  dalam  pengolahan  teks  dan pengembangan aplikasi yang memerlukan identifikasi pola tertentu. Dalam konteks tertentu, seperti mencari lokasi gerai Indomaret di berbagai kota di Indonesia, pencarian pola menjadi krusial. Implementasi algoritma string matching adalah salah satu pendekatan yang efektif untuk menyelesaikan permasalahan tersebut.
Algoritma  string  matching  adalah  algoritma  yang  digunakan  untuk  mencari keberadaan sebuah pola (pattern) dalam sebuah teks. Beberapa algoritma string matching yang umum digunakan antara lain adalah Brute Force, Knuth-Morris-Pratt (KMP), dan Boyer- Moore.  Dalam  implementasi  pencarian  nama  "Indomaret"  di  teks  yang  berisi  nama-nama kota di Indonesia, algoritma KMP atau Boyer-Moore mungkin menjadi pilihan yang efisien karena kemampuannya dalam mengurangi jumlah pembandingan yang diperlukan.

## Praproses
Sebelum  proses  pencarian  dimulai,  teks  dan  pola  yang  akan  dicari  perlu  diproses terlebih dahulu. Praproses ini melibatkan pengubahan teks dan pola menjadi format yang

## Implementasi Algoritma Greedy dan String Matching Penukaran Uang Menjadi Koin,
Pencarian Pola dalam Teks yang Berisi Nama ”Indomaret” – Muhammad Arif Afandy  et.al
lebih mudah untuk diproses. Misalnya, teks dan pola dapat diubah menjadi huruf kecil semua untuk mengurangi kompleksitas pencarian. Praproses juga dapat melibatkan pembuangan karakter khusus atau langkah-langkah lain untuk meningkatkan efisiensi pencarian.
Setelah praproses selesai, algoritma string matching dipilih dan diimplementasikan. Langkah-langkah  algoritma  dilakukan  untuk  mencari  pola  "Indomaret"  dalam  teks  yang berisi nama-nama kota di Indonesia. Algoritma melakukan pemindaian (scanning) teks secara sistematis dan membandingkan setiap karakter teks dengan pola yang dicari. Saat pola cocok ditemukan, posisi kemunculannya akan dicatat.
Dalam implementasi pencarian nama "Indomaret" di teks, ada beberapa kasus khusus yang perlu dipertimbangkan. Misalnya, penanganan huruf besar-kecil (case insensitivity) dan kemungkinan adanya variasi.

## CONCLUSION
Dari  hasil  penelitian  ini,  dapat  disimpulkan  bahwa  penggunaan  algoritma  Greedy dalam proses penukaran uang di Indomaret menawarkan pendekatan yang efisien dan cepat dalam mengelola proses penukaran uang bagi pelanggan. Implementasi algoritma Greedy memungkinkan  Indomaret  untuk  memaksimalkan  penggunaan  stok  uang  yang  tersedia dengan memprioritaskan penukaran uang dengan denominasi tertinggi terlebih dahulu. Hal ini menghasilkan jumlah uang kembalian yang optimal bagi pelanggan dan mengoptimalkan penggunaan stok uang tunai Indomaret. Meskipun demikian, perlu diingat bahwa algoritma Greedy  bukanlah  solusi  yang  sempurna dalam semua  situasi, dan  kemungkinan  terdapat kekurangan  dalam  stok  uang  yang  tersedia  atau  pola  permintaan  pelanggan  yang  tidak sesuai dengan strategi algoritma Greedy yang diterapkan.
Sementara itu, penggunaan algoritma String Matching, khususnya algoritma Knuth- Morris-Pratt  (KMP),  dalam  pencarian  cabang  Indomaret  di  berbagai  kota  di  Indonesia, memberikan  cara  yang  efisien  untuk  menemukan  lokasi  cabang  Indomaret  yang  terdekat dengan pelanggan. Algoritma KMP menawarkan kompleksitas waktu yang rendah dalam mencocokkan pola dalam teks, memungkinkan Indomaret untuk dengan mudah mencari dan menemukan kemunculan nama cabangnya dalam data cabang Indomaret di berbagai kota di Indonesia.  Meskipun  demikian,  variasi  yang  signifikan  dalam  kinerja  algoritma  String Matching  perlu  dipertimbangkan,  dan  evaluasi  lebih  lanjut  mungkin  diperlukan  untuk memahami  penyebab  variasi  tersebut  dan  mengidentifikasi  cara  untuk  meningkatkan stabilitasnya.

## REFERENCE
Ahmad, I., Borman, R. I., Caksana, G. G., & Fakhrurozi, J. (2021). Implementasi String Matching Dengan Algoritma Boyer-Moore Untuk Menentukan Tingkat Kemiripan Pada Pengajuan Judul  Skripsi/Ta  Mahasiswa  (Studi  Kasus:  Universitas  XYZ). SINTECH  (Science  and Information Technology) Journal , 4 (1), 53 – 58.
Anggreani, D., Putri, D. P. I., Handayani, A. N., & Azis, H. (2020). Knuth Morris Pratt algorithm in  enrekang-indonesian  language  translator. International  Conference  on  Vocational Education and Training (ICOVET) , 144 – 148.
Charalampopoulos,  P.,  Kociumaka,  T.,  &  Wellnitz,  P.  (2020).  Faster  approximate  pattern matching: A unified approach. Annual Symposium on Foundations of Computer Science

## Implementasi Algoritma Greedy dan String Matching Penukaran Uang Menjadi Koin,
Pencarian Pola dalam Teks yang Berisi Nama ”Indomaret” – Muhammad Arif Afandy  et.al
(FOCS) , 978 – 989.
Commentz-Walter, B. (1979). A string matching algorithm fast on the average. International Colloquium on Automata, Languages, and Programming, Springer , 118 – 132. Darnila, E., Ula, M., & Soraya, C. D. A. (2019). Optimasi Kelayakan Kondisi Pembangunan Jalan  di  Kota  Lhokseumawe  Menggunakan  Algoritma  Greedy. JUKI:  Jurnal  Komputer Dan Informatika , 1 (1), 9 – 14.
Ilham,  M.,  &  Mirza,  A.  H.  (2020).  Penerapan  Algoritma  Knuth  Morris  Pratt  Dalam  Fitur Pencarian  Pengarsipan  Dokumen  Pada  Sma  Plus  Negeri  17  Palembang. Journal  of Software Engineering Ampera , 1 (2), 110 – 121.
Janson, L., Ichter, B., & Pavone, M. (2018). Deterministic sampling-based motion planning:
Optimality, complexity, and performance. Int J Rob Res , 37 (1), 46 – 61.
Nizar,  A.,  Harsani,  P.,  &  Anggraeni,  I.  (2024).  Robot  Virtual  Menggunakan  Metode  Knuth Morris  Pratt:  Virtual  Robot  Using  Knuth  Morris  Pratt  Method. MALCOM:  Indonesian Journal of Machine Learning and Computer Science , 4 (1), 282 – 292.
Roihan,  A.,  Nasution,  K.,  &  Siambaton,  M.  Z.  (2022).  Implementasi  Algoritma  Greedy Kombinasi dengan Perulangan pada Aplikasi Penjadwalan Praktikum,” ,. Sudo Jurnal Teknik Informatika , 1 (2), 42 – 50.
Ruiz,  R.,  &  Stützle,  T.  (2007).  A  simple  and  effective  iterated  greedy  algorithm  for  the permutation flowshop scheduling problem. Eur J Oper Res , 177 (3), 2033 – 2049.
Septiana, R. D., Punkastyo, D. A., & Nugroho, N. (2022). Implementasi Algoritma Greedy dan Algoritma  A*  Untuk  Penentuan  Cost  Pada  Routing  Jaringan. KLIK:  Kajian  Ilmiah Informatika Dan Komputer , 3 (2), 181 – 187. Vince, A. (2002). A framework for the greedy algorithm. Discrete Appl Math (1979) , 121 (1 – 3), 247 – 260.
Zhang, Z., Schwartz, S., Wagner, L., & Miller, W. (2000). A greedy algorithm for aligning DNA sequences. Journal of Computational Biology , 7 (1 – 2), 203 – 214.