ក្បួនដោះស្រាយរ៉ាប៊ីន-កាបសម្រាប់ការស្វែងរកលំនាំនៅក្នុងម៉ាទ្រីស

ប្លុក

បានផ្តល់ឱ្យម៉ាទ្រីស txt [] [] នៃវិមាត្រ ម ១ x ម ២ និងលំនាំ ប៉ាត់ [] [] នៃវិមាត្រ n1 x n2 ភារកិច្ចគឺត្រូវពិនិត្យមើលថាតើមានលំនាំមួយនៅក្នុងម៉ាទ្រីសរឺអត់ហើយប្រសិនបើបាទ / ចាសបន្ទាប់មកបោះពុម្ពព្រីនធ័រខាងលើ។ ប៉ាត់ [] [] នៅក្នុង txt [] [] ។ វាត្រូវបានសន្មត់ថា m1, m2 ≥ n1, n2



ប្រធានបទល្អបំផុតសម្រាប់ vscode

ឧទាហរណ៍:

Input: txt[][] = {{G, H, I, P} {J, K, L, Q} {R, G, H, I} {S, J, K, L} } pat[][] = {{G, H, I}, {J, K, L} } Output: Pattern found at ( 0, 0 ) Pattern found at ( 2, 1 ) Explanation:

បញ្ចូល៖
txt [] [] = {{A, B, C},
{ឃ, អ៊ី, អេហ្វ),
{G, H, ខ្ញុំ}
}
ប៉ាត់ [] [] = {{អ៊ី, អេហ្វ),
{ហ, ខ្ញុំ}
}
លទ្ធផល៖
លំនាំបានរកឃើញនៅ (១, ១)



**Approach:** In order to find a pattern in a 2-D array using [Rabin-Karp algorithm](https://www.geeksforgeeks.org/rabin-karp-algorithm-for-pattern-searching/), consider an input matrix **txt[m1][m2]** and a pattern **pat[n1][n2]**. The idea is to find the [hash](https://www.geeksforgeeks.org/hashing-data-structure/) of each columns of **mat[][]** and **pat[][]** and compare the hash values. For any column if hash values are equals than check for the corresponding rows values. Below are the steps: 1. Find the hash values of each column for the first **N1** rows in both **txt[][]** and **pat[][]** matrix. 2. Apply Rabin-Karp Algorithm by finding hash values for the column hashes found in step 1. 3. If a match is found compare **txt[][]** and **pat[][]** matrices for the specific rows and columns. 4. Else slide down the column hashes by 1 row in the txt matrix using a [rolling hash](https://www.geeksforgeeks.org/string-hashing-using-polynomial-rolling-hash-function/). 5. Repeat steps 2 to 4 for all the hash values and if we found any **pat[][]** match in **txt[][]** then print the indices of top most cell in the **txt[][]**. **To find the hash value:** In order to find the hash value of a substring of size **N** in a text using rolling hash follow below steps: 1. Remove the first character from the string: **hash(txt[s:s+n-1])-(radix**(n-1)*txt[s])%prime_number** 2. Add the next character to the string: **hash(txt[s:s+n-1])*radix + txt[n]**

#មហន្តរាយ #ហាស #គណិតវិទ្យា #ម៉ាទ្រីស #ស្វែងរក #ក្បួនដោះស្រាយ

www.geeksforgeeks.org

ក្បួនដោះស្រាយរ៉ាប៊ីន-កាបសម្រាប់ការស្វែងរកលំនាំនៅក្នុងម៉ាទ្រីស

វិបផតថលវិទ្យាសាស្ត្រកុំព្យូទ័រសម្រាប់អ្នកមើល។ វាមានសរសេរបានល្អគិតបានល្អនិងពន្យល់បានល្អអំពីវិទ្យាសាស្ត្រកុំព្យូទ័រនិងអត្ថបទកម្មវិធីកម្រងសំណួរ