cari
Rumahpembangunan bahagian belakangC++Program C algoritma Rabin-Karp untuk carian corak

Program C algoritma Rabin-Karp untuk carian corak

Padanan corak dalam C - Kita perlu mencari jika rentetan wujud dalam rentetan lain, sebagai contoh, rentetan "algoritma" wujud dalam rentetan "algoritma naif". Jika ia ditemui, maka lokasinya (iaitu di mana ia terletak) dipaparkan. Kami cenderung untuk mencipta fungsi yang mengambil tatasusunan 2 aksara dan mengembalikan kedudukan jika terdapat padanan Jika tidak, -1 dikembalikan.

Input: txt = "HERE IS A NICE CAP"
   pattern = "NICE"
Output: Pattern found at index 10
Input: txt = "XYZXACAADXYZXYZX"
   pattern = "XYZX"
Output: Pattern found at index 0
   Pattern found at index 9
   Pattern found at index 12

Rabin-Karp ialah satu lagi algoritma carian corak. Hanya padanan rentetan Algoritma yang dicadangkan oleh Rabin dan Karp untuk mencari corak dengan lebih cekap Cara. Seperti algoritma naif, ia juga menyemak corak dengan menggerakkan tetingkap Ia mencari cincang satu demi satu, tetapi tidak perlu menyemak semua aksara dalam semua kes. Apabila cincang sepadan, setiap aksara disemak. Dengan cara ini, hanya terdapat satu perbandingan bagi setiap urutan teks, menjadikannya algoritma carian corak yang lebih cekap.

Masa prapemprosesan - O(m)

Kerumitan masa algoritma Rabin-Karp ialah O(m+n ) , tetapi untuk senario terburuk, Ia adalah O(mn).

Algoritma

rabinkarp_algo(teks, corak, perdana)

Input#🎟#🎜🎜🎜🎜🎜🎜🎜 corak, perdana)

Input

kuat>− Teks dan corak. Cari nombor perdana lain pada kedudukan cincang

Output

− Cari kedudukan corak

Start
   pat_len := pattern Length
   str_len := string Length
   patHash := 0 and strHash := 0, h := 1
   maxChar := total number of characters in character set
for index i of all character in the pattern, do
   h := (h*maxChar) mod prime
for all character index i of pattern, do
   patHash := (maxChar*patHash + pattern[i]) mod prime
   strHash := (maxChar*strHash + text[i]) mod prime
for i := 0 to (str_len - pat_len), do
   if patHash = strHash, then
      for charIndex := 0 to pat_len -1, do
         if text[i+charIndex] ≠ pattern[charIndex], then
         break
if charIndex = pat_len, then
   print the location i as pattern found at i position.
if i < (str_len - pat_len), then
   strHash := (maxChar*(strHash &ndash; text[i]*h)+text[i+patLen]) mod prime, then
   if strHash < 0, then
   strHash := strHash + prime
End
Contoh#🎜#🎜##🎜 Demo langsung

#include<stdio.h>
#include<string.h>
int main (){
   char txt[80], pat[80];
   int q;
   printf ("Enter the container string </p><p>");
   scanf ("%s", &txt);
   printf ("Enter the pattern to be searched </p><p>");
   scanf ("%s", &pat);
   int d = 256;
   printf ("Enter a prime number </p><p>");
   scanf ("%d", &q);
   int M = strlen (pat);
   int N = strlen (txt);
   int i, j;
   int p = 0;
   int t = 0;
   int h = 1;
   for (i = 0; i < M - 1; i++)
      h = (h * d) % q;
   for (i = 0; i < M; i++){
      p = (d * p + pat[i]) % q;
      t = (d * t + txt[i]) % q;
   }
   for (i = 0; i <= N - M; i++){
      if (p == t){
         for (j = 0; j < M; j++){
            if (txt[i + j] != pat[j])
            break;
         }
         if (j == M)
            printf ("Pattern found at index %d </p><p>", i);
      }
      if (i < N - M){
         t = (d * (t - txt[i] * h) + txt[i + M]) % q;
         if (t < 0)
            t = (t + q);
      }
   }
   return 0;
}

output

Enter the container string
tutorialspointisthebestprogrammingwebsite
Enter the pattern to be searched
p
Enter a prime number
3
Pattern found at index 8
Pattern found at index 21

Atas ialah kandungan terperinci Program C algoritma Rabin-Karp untuk carian corak. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!

Kenyataan
Artikel ini dikembalikan pada:tutorialspoint. Jika ada pelanggaran, sila hubungi admin@php.cn Padam
C程序计算3D空间中三个点之间的距离C程序计算3D空间中三个点之间的距离Aug 29, 2023 pm 12:41 PM

给定一个三维平面,因此有三个坐标,任务是找到给定点之间的距离并显示结果。在三维平面上,有三个坐标轴,x轴的坐标为(x1,y1,z1),y轴的坐标为(x2,y2,z2),z轴的坐标为(x3,y3,z)。计算它们之间的距离有一个直接的公式如下所示$$\sqrt{\lgroupx2-x1\rgroup^{2}+\lgroupy2-y1\rgroup^{2}+\lgroupz2-z1\rgroup^{2}}$$下面是表示三个不同坐标轴及其坐标的图示下面使用的方法如下&minus;输入坐标(x1,

二项式系数表的C程序二项式系数表的C程序Aug 26, 2023 pm 12:49 PM

Givenwithapositiveintegervaluelet&rsquo;ssay&lsquo;val&rsquo;andthetaskistoprintthevalueofbinomialcoefficientB(n,k)where,nandkbeanyvaluebetween0tovalandhencedisplaytheresult.WhatisBinomialCoefficientBinomialcoefficient(n,k)istheorderofcho

最小成本路径的C程序最小成本路径的C程序Aug 26, 2023 pm 06:17 PM

在这里,我们将解决C语言中的最小成本路径问题。这意味着在2D矩阵上完成,其中每个单元格都有一个移动成本。我们必须找到一条从左上角到右下角且行程成本最小的路径。您只能从给定单元格向下和右下遍历单元格。为了解决这个特定问题,动态编程比递归更好。给定成本矩阵cost[][]和位置(m,n),我们必须编写一个函数,返回从(0,0)到达(m,n)的最小路径成本到达(m,n)的路径的总成本是该路径上所有成本的总和(包括源和目的地)。假设−所有成本是积极的。输入矩阵中不存在负成本循环示例查找到(2,2)的最小

在C语言中编写一个程序,打印出N个五角数的序列在C语言中编写一个程序,打印出N个五角数的序列Aug 25, 2023 pm 02:25 PM

程序说明五维体数是帕斯卡三角形的任意一行中第五个数字,从左到右或从右到左开始,起始于5项行14641。这种数字的前几个是1,5,15,35,70,126,210,330,495,715,1001,1365Pentatopenumbersbelongintheclassoffiguratenumbers,whichcanberepresentedasregular,discretegeometricpatterns.Theformulaforthenthpentatopicnumberis$$\l

C++程序以找到给定值的反正切C++程序以找到给定值的反正切Aug 26, 2023 am 10:09 AM

我们在三角学中最常使用的比率包括正弦、余弦、正切等等。您可以使用角度来计算这些比率。如果我们知道比率值,我们还可以使用反三角函数计算角度。本课程将向您展示如何使用C++的反正切(arctan)函数,使用正切值(以弧度为单位)计算角度。atan()函数使用atan()技术和反三角正切函数计算角度。C++标准库包含这个函数。在使用这种方法之前,我们必须导入cmath库。此方法返回以弧度为单位的角度,并采用正切值作为参数。以下使用简单的语法-语法#include<cmath>atan(&l

C++程序:替换特定索引处的字符C++程序:替换特定索引处的字符Aug 25, 2023 pm 10:53 PM

字符串是一组字符。我们也可以将它们称为字符数组。考虑到一个由字符串组成的字符数组,这些字符串具有指定的索引和值。有时候我们可以对字符串进行一些修改,其中一种修改是替换字符通过提供一个特定的索引。在本文中,我们将看到如何替换一个字符从一个specificindexinsideastringusingC++.语法String_variable[&lt;givenindex&gt;]=&lt;newcharacter&gt;在C++中,我们可以使用索引访问字符串字符。在

计算六边形内切圆内的正方形面积的C程序计算六边形内切圆内的正方形面积的C程序Aug 28, 2023 pm 08:41 PM

给定一个正六边形内接的圆内切的正方形,我们需要找到正方形的面积,为此我们需要找到正方形边长和正六边形边长之间的关系。正六边形内接圆的半径的数学公式为,r=A&radic;3/2由于正方形的对角线等于圆的直径,所以半径和边长之间的关系为,a=&radic;r根据正六边形的边长,a=&radic;3A/&radic;2所以,正方形的面积,面积=a2=(&radic;3A/&radic;2)2示例#include<stdio.h>#inclu

Rabin-Karp算法的C程序用于模式搜索Rabin-Karp算法的C程序用于模式搜索Sep 17, 2023 am 09:01 AM

C中的模式匹配-我们必须查找一个字符串是否存在于另一个字符串中,例如,字符串“algorithm”存在于字符串“naivealgorithm”中。如果是找到,然后显示它的位置(即它所在的位置)。我们倾向于创建一个接收2个字符数组的函数,如果匹配则返回位置否则返回-1。Input:txt="HEREISANICECAP"&nbsp;&nbsp;pattern="NICE"Output:Patternfoundatindex10Input:tx

See all articles

Alat AI Hot

Undresser.AI Undress

Undresser.AI Undress

Apl berkuasa AI untuk mencipta foto bogel yang realistik

AI Clothes Remover

AI Clothes Remover

Alat AI dalam talian untuk mengeluarkan pakaian daripada foto.

Undress AI Tool

Undress AI Tool

Gambar buka pakaian secara percuma

Clothoff.io

Clothoff.io

Penyingkiran pakaian AI

AI Hentai Generator

AI Hentai Generator

Menjana ai hentai secara percuma.

Artikel Panas

R.E.P.O. Kristal tenaga dijelaskan dan apa yang mereka lakukan (kristal kuning)
3 minggu yang laluBy尊渡假赌尊渡假赌尊渡假赌
R.E.P.O. Tetapan grafik terbaik
3 minggu yang laluBy尊渡假赌尊渡假赌尊渡假赌
R.E.P.O. Cara Memperbaiki Audio Jika anda tidak dapat mendengar sesiapa
3 minggu yang laluBy尊渡假赌尊渡假赌尊渡假赌

Alat panas

Penyesuai Pelayan SAP NetWeaver untuk Eclipse

Penyesuai Pelayan SAP NetWeaver untuk Eclipse

Integrasikan Eclipse dengan pelayan aplikasi SAP NetWeaver.

ZendStudio 13.5.1 Mac

ZendStudio 13.5.1 Mac

Persekitaran pembangunan bersepadu PHP yang berkuasa

MantisBT

MantisBT

Mantis ialah alat pengesan kecacatan berasaskan web yang mudah digunakan yang direka untuk membantu dalam pengesanan kecacatan produk. Ia memerlukan PHP, MySQL dan pelayan web. Lihat perkhidmatan demo dan pengehosan kami.

Pelayar Peperiksaan Selamat

Pelayar Peperiksaan Selamat

Pelayar Peperiksaan Selamat ialah persekitaran pelayar selamat untuk mengambil peperiksaan dalam talian dengan selamat. Perisian ini menukar mana-mana komputer menjadi stesen kerja yang selamat. Ia mengawal akses kepada mana-mana utiliti dan menghalang pelajar daripada menggunakan sumber yang tidak dibenarkan.

SublimeText3 versi Mac

SublimeText3 versi Mac

Perisian penyuntingan kod peringkat Tuhan (SublimeText3)