Mönstermatchning används ofta inom datavetenskap och många andra områden. Mönstermatchningsalgoritmer används för att söka efter mönster i en större text eller datauppsättning. En av de mest populära algoritmerna för mönstermatchning är Boyer-Moore algoritm, som publicerades första gången 1977. I den här artikeln kommer vi att diskutera Pattern Matching-algoritmer i C och hur de fungerar.
Vad är en mönstermatchningsalgoritm?
Mönstermatchningsalgoritmer används för att hitta mönster inom en större uppsättning data eller text. Dessa algoritmer fungerar genom att jämföra ett mönster med en större datamängd eller text och avgöra om mönstret finns eller inte. Mönstermatchningsalgoritmer är viktiga eftersom de tillåter oss att snabbt söka efter mönster i stora datamängder.
java sträng längd
Brute Force Pattern Matching Algoritm:
Brute Force Pattern Matching är den enklaste Pattern Matching Algorithm. Det går ut på att jämföra karaktärerna i mönstret med tecknen i texten en efter en. Om alla tecken matchar, returnerar algoritmen startpositionen för mönstret i texten. Om inte, flyttar algoritmen till nästa position i texten och upprepar jämförelsen tills en matchning hittas eller slutet av texten nås. Tidskomplexiteten för Brute Force Algorithm är O(MXN) , var M anger längden på texten och N anger mönstrets längd.
Naiv mönstermatchningsalgoritm:
Algoritmen för Naive Pattern Matching är en förbättring jämfört med Brute Force-algoritmen. Det undviker onödiga jämförelser genom att hoppa över vissa positioner i texten. Algoritmen börjar jämföra mönstret med texten vid den första positionen. Om tecknen matchar flyttas den till nästa position och upprepar jämförelsen. Om tecknen inte stämmer överens flyttar algoritmen till nästa position i texten och jämför mönstret med texten igen. Tidskomplexiteten för den naiva algoritmen är också O(MXN) , men det är snabbare än Brute Force-algoritmen i de flesta fall.
Knuth-Morris-Pratt Algoritm:
De Knuth-Morris-Pratt (KMP) algorithm är en mer avancerad mönstermatchningsalgoritm. Den bygger på observationen att när en missmatchning uppstår kan viss information om texten och mönstret användas för att undvika onödiga jämförelser. Algoritmen förberäknar en tabell som innehåller information om mönstret. Tabellen bestämmer hur många tecken i mönstret som kan hoppas över när en missmatchning uppstår. Tidskomplexiteten hos KMP algoritm är O(M+N) .
Boyer-Moore-algoritmen:
En av de mest populära mönstermatchningsalgoritmerna är Boyer-Moore algoritm. Denna algoritm publicerades första gången 1977 av Robert S. Boyer och J Strother Moore. De Boyer-Moore algoritm jämför ett mönster med en större uppsättning data eller text från höger till vänster istället för från vänster till höger, som med de flesta andra mönstermatchningsalgoritmer.
De Boyer-Moore Algoritmen har två huvudkomponenter: regeln för dåliga tecken och regeln för bra suffix. Regeln om dåliga tecken fungerar genom att tecknet i mönstret jämförs med motsvarande tecken i data eller text. Om tecknen inte stämmer överens, flyttar algoritmen mönstret till höger tills den hittar ett tecken som matchar. Regeln för bra suffix jämför suffixet för mönstret med motsvarande suffix för data eller text. Om suffixen inte matchar, flyttar algoritmen mönstret åt höger tills den hittar ett matchande suffix.
De Boyer-Moore Algoritmen är känd för sin effektivitet och används ofta i många applikationer. Det anses vara en av de snabbaste mönstermatchningsalgoritmerna som finns tillgängliga.
Implementering av Boyer-Moore-algoritmen i C:
För att genomföra Boyer-Moore algoritm i C, kan vi börja med att definiera regeln om dåliga tecken. Vi kan använda en array för att lagra den sista förekomsten av varje tecken i mönstret. Denna array kan avgöra hur långt vi måste flytta mönstret åt höger när en missmatchning inträffar.
Här är ett exempel på hur vi kan implementera regeln om dålig karaktär i C:
hur många städer finns det i usa
C-kod:
void bad_character_rule(char *pattern, int pattern_length, int *bad_char) { int i; for (i = 0; i <no_of_chars; i++) bad_char[i]="-1;" for (i="0;" i < pattern_length; bad_char[(int) pattern[i]]="i;" } pre> <p>In this example, we first initialize the array to -1 for all characters. We then iterate through the pattern and update the array with the last occurrence of each character in the pattern.</p> <p>Next, we can implement the good suffix rule. We can use an array to store the length of the longest suffix of the pattern that matches a suffix of the data or text. This array can be used to determine how far we need to move the pattern to the right.</p> <hr></no_of_chars;>