Abstrakt. En algoritm presenteras som finner alla förekomster av en. given sträng inom en annan, i körtid proportionell mot summan av strängarnas längder. Kontinuerligheten av proportionalitet är tillräckligt låg för att göra denna algoritm av praktisk användning, och förfarandet kan också utvidgas för att hantera några mer allmänna mönstermatchning problem. En teoretisk tillämpning av algoritmen visar att uppsättningen konkatenationer av även palindromer, dvs. språket {kan}*, kan kännas igen i linjär tid. Andra algoritmer som körs ännu snabbare i genomsnitt beaktas också. Nyckelord, mönster, sträng, text-redigering, mönster-matchning, trie minne, sökning, period av en sträng, palindrom, optimal algoritm, Fibonacci sträng, reguljärt uttryck Text-redigering program krävs ofta för att söka igenom en sträng av tecken som letar efter fall av en given "mönster" sträng; Vi vill hitta alla positioner, eller kanske bara den vänstra position, där mönstret förekommer som en sammanhängande substring av texten. Till exempel, c a e n a r y innehåller mönstret e n, men vi betraktar inte c a n a r y som en delsträng. Det uppenbara sättet att söka efter ett matchande mönster är att försöka söka på varje utgångspunkt i texten, överge sökningen så snart en felaktig karaktär hittas. Men detta tillvägagångssätt kan vara mycket ineffektivt, till exempel när vi letar efter en förekomst av aaaaaab i aaaaaaaaaaaaaaaaaaab. När mönstret är a"b och texten är a2"b, kommer vi att hitta oss göra (n + 1) jämförelser av tecken. Dessutom innebär det traditionella tillvägagångssättet att "backa upp" den ingående texten när vi går igenom den, och detta kan ge irriterande komplikationer när vi överväger de buffertoperationer som ofta är inblandade. I detta papper beskriver vi en mönstermatchning algoritm som finner alla förekomster av ett mönster av längd rn inom en text av längd n i O(rn + n) enheter av tid, utan att "backa upp" indatatexten. Algoritmen behöver endast O(m) platser för internt minne om texten läses från en extern fil, och endast O(log m) enheter av tid förflyter mellan på varandra följande ensiffriga ingångar. Alla de proportionalitetskonstanter som dessa O-formler antyder är oberoende av alfabetets storlek.
Den välkända KMP-algoritmen REF använde ursprungligen periodiska strukturer för att söka efter mönster i en text.
FAST PATTERN MATCHING IN STRINGS*
{'venue': None, 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}