Naive pattern matching — O(nm): Question bank — Hinglish deep dive

3.8.1 · D5 · Coding › String Algorithms › Naive pattern matching — O(nm)

Ye bank naive pattern matching ki boundaries aur misconceptions drill karta hai. Algorithm ki machinery ke liye parent note dekho; iske weaknesses fix karne wale algorithms ke liye KMP Algorithm, Boyer-Moore Algorithm, aur Rabin-Karp Algorithm dekho.

In questions mein jo vocabulary use hoti hai

Koi bhi trap try karne se pehle, un paanch symbols ko pakad lo jo har jagah neeche dikhenge. Inme se har ek kisi specific cheez ka naam hai jise tum point kar sakte ho.

Formula Woh algorithm jis par is poori page ke questions based hain

Yeh exact naive matcher hai jis par neeche ke har sawal based hain. Ise saamne rakho.

def naive_match(T, P):
    n = len(T)          # length of the text
    m = len(P)          # length of the pattern
    for s in range(n - m + 1):     # each candidate shift 0 .. n-m
        j = 0
        while j < m and T[s + j] == P[j]:   # compare, break on mismatch
            j = j + 1
        if j == m:                  # inner loop ran to completion
            report_match(s)         # all m characters lined up

Outer loop (for s): $P$ ko har legal start position par slide karta hai.
Inner while: $P$ ko $T$ ke against spell karta hai, jaise hi $T [s + j] \neq = P [j]$ hota hai rok deta hai (early break).
Success test j == m: tabhi reach hota hai jab saare $m$ characters match ho jaate hain.

Neeche ki figure ek matching shift aur ek failing shift dikhati hai taaki tum "slide" aur "spell" ka matlab picture kar sako.

True ya false — justify karo

Naive matching ek valid match miss kar sakta hai agar pattern do baar ek saath aaye.

False — outer loop har shift

0

n - m

tak try karta hai, toh overlapping ya back-to-back occurrences sab independently milte hain; correctness exhaustion se hai.

Candidate shifts ki sankhya

n

hai.

False — yeh ==

n - m + 1

== hai, positions

0

n - m

tak; baad mein start karne par pattern text ke end se bahar nikal jaayega.

Early break yeh change karta hai ki algorithm kaun se matches report karta hai.

False — break sirf mismatch ke baad comparing band karta hai, jo waise bhi fail hoti; yeh kaam bachata hai lekin exactly same shifts report karta hai.

Naive matching hamesha

O (nm)

hoti hai.

False —

O (nm)

worst case hai; typical text par mismatches pehle ya doosre char mein hi ho jaati hain, toh average par yeh

O (n)

ke kareeb behave karta hai.

Agar

m > n

ho toh algorithm zero matches report karta hai.

True — loop range(n - m + 1) empty ho jaata hai (uska argument

\leq 0

hai), toh koi bhi shift test nahi hoti, jo sahi hai kyunki pattern fit hi nahi ho sakta.

Early break hatane se algorithm incorrect ho jaata hai.

False — break ke bina bhi sahi answers milte hain; bas har shift par poore

m

comparisons hote hain, time waste hota hai lekin accuracy nahi jaati.

Naive matching uss characters ko reuse karta hai jo pichle shift mein already compare ho chuke hain.

False — yeh deliberately sab kuch bhool jaata hai aur har shift par

j = 0

se restart karta hai; us information ko reuse karna exactly KMP Algorithm ki taraf ka leap hai.

Ek empty pattern (

m = 0

) ko har position par match report karna chahiye.

True —

m = 0

ke saath, range(n - m + 1) range(n+1) hai, toh

n + 1

shifts hain (

0

n

tak) aur inner while zero baar chalta hai, har shift ko vacuously valid banaata hai; yeh conventional convention hai.

Worst case mein text aur pattern mein koi common characters nahi hote.

False — worst case ko near-matches chahiye, jaise text "AAAA…A" aur pattern "AAA…B", taaki last mismatch se pehle bahut saare chars match ho jaayein — inner-loop work maximize ho.

Error dhundo

for s in range(n): outer loop bound ke roop mein.

s > n - m

par, access

T [s + j]

out of bounds ho jaata hai (index

n - 1

ke aage); sahi bound hai range(n - m + 1) taaki pattern text se bahar na nikal jaaye.

"Maine saare

m

chars compare kiye aur 3 match hue, toh main

s + 3

skip kar lunga."

Yeh sahi instinct lekin galat algorithm hai — naive matching shifts ke across partial info carry nahi karta; matched prefixes ke basis par aage skip karna KMP Algorithm optimization hai, naive nahi.

Inner loop likha while j <= m and T[s+j]==P[j]:.

Bound j < m (strict) hona chahiye;

j = m

par koi

P [m]

nahi hai (valid indices

0

m - 1

tak hain), toh <= pattern ke end se aage padhta hai aur off-by-one hai.

Match tab hi report karo jab j > m.

Success test j == m hai: inner loop

j

m

tak pahunchte hi ruk jaata hai (saare chars match), toh

j

kabhi

m

se zyada nahi hota; j > m kuch bhi report nahi karta.

"Outer loop dominant hai, toh cost

O (n - m + 1)

hai."

Inner loop har outer step par up to

m

comparisons karta hai, toh multiply karo:

(n - m + 1) \cdot m

, jo

O (nm)

deta hai — inner work ko ignore nahi kar sakte.

Poore substrings T[s:s+m] == P se compare karo aur use

O (n)

kaho.

Slice-and-compare andar se phir bhi

O (m)

per shift cost karta hai, toh total abhi bhi

O (nm)

hai; loop ko library call mein chhupane se complexity nahi badlti.

Why questions

Outer loop

n - m

par kyun ruk jaata hai

n - 1

ki jagah?

Kyunki length

m

ka pattern shift

s

par start hokar positions

s

s + m - 1

tak occupy karta hai; agar

s > n - m

ho toh woh aakhri index

n - 1

se aage nikal jaata hai aur simply

m

characters bache nahi hote.

Naive matching "correct by exhaustion" kyun hai?

Yeh har possible starting position test karta hai aur har par saare

m

characters check karta hai, toh koi valid shift slip through nahi ho sakta — completeness sab candidates try karne se aati hai.

Algorithm har nayi shift par

j = 0

se restart kyun karta hai?

Design se yeh har shift ko ek independent question maanta hai aur koi memory nahi rakhta; yahi simplicity ise naive banati hai aur KMP Algorithm se slower bhi.

Same algorithm English par

O (n)

lekin "AAAA" par

Θ (nm)

kyun ho sakta hai?

English par mismatches almost immediately fire hote hain (chhote inner loops); repetitive text par inner loop last char tak match karta rehta hai, toh har shift par poora

m

pay karna padta hai.

Early break ek optimization kyun hai, correctness fix nahi?

Pehla mismatch already guarantee karta hai ki yeh shift fail hogi, toh continue karna sirf failure confirm karta — break comparisons bachata hai lekin identical verdict tak pahunchta hai.

Alphabet bada hone par practice mein naive matching tend kyun karta hai faster hone ke liye?

Zyada distinct symbols first-character mismatch zyada likely banate hain, toh inner loop usually ek comparison ke baad exit kar jaata hai, average behavior ko

O (n)

ke kareeb le jaata hai.

Naive matching ko sliding window

O (1)

per step kyun classify nahi kiya jaata?

Ek true sliding window har move par constant time mein state update karta hai; naive har slide par up to

m

characters re-scan karta hai, toh har "window move"

O (m)

cost karta hai,

O (1)

nahi.

Edge cases

Jab pattern poore text ke barabar ho (

m = n

) toh algorithm kya output karta hai?

Exactly ek shift test hoti hai (

s = 0

, kyunki range(n-m+1) range(1) hai), aur woh match karta hai, toh

s = 0

par ek single match report hoti hai.

Empty text (

n = 0

) par non-empty pattern ke saath kya hota hai?

range(n - m + 1) ka argument

\leq 0

hai toh yeh empty hai; koi comparison nahi chalta aur koi match report nahi hota, jo sahi hai.

Jab dono text aur pattern empty hon (

n = 0

aur

m = 0

) toh kya hota hai?

range(n - m + 1) range(1) ban jaata hai, toh exactly shift

s = 0

test hoti hai; inner while zero baar chalta hai, toh j == m (dono

0

) succeed karta hai aur

s = 0

par ek match report hota hai — empty pattern empty text mein position 0 par milta hai.

Agar pattern single character ka ho (

m = 1

), toh complexity kya hai?

Inner loop har shift par at most ek comparison hai, jo

(n - 1 + 1) \cdot 1 = n

steps deta hai, yaani

O (n)

— us character ke liye ek linear scan.

s = n - m

(bilkul aakhri legal shift) par match report hoti hai kya?

Haan — range(n-m+1) mein

n - m

included hai, toh final aligned position kisi bhi aur shift ki tarah test hoti hai aur match hone par report hoti hai.

Kya do reported matches text mein overlap kar sakte hain?

Haan — jaise

P =

"ABA" in

T =

"ABABA"

s = 0

aur

s = 2

par match karta hai, jo overlap karte hain; algorithm har ek independently report karta hai kyunki woh har shift check karta hai.

Agar

T

ka har character

P

ke har character ke barabar ho (dono "A" se bhare)?

n - m + 1

mein se har ek shift valid hogi aur har ek phir bhi poore

m

comparisons karta hai, toh sab shifts report hoti hain maximum

Θ (nm)

cost par.

Recall Traps ka ek-line summary

Boundary $n - m$ dhyan rakho, worst case ko average se kabhi confuse mat karo, aur yaad rakho break time bachata hai correctness nahi — jis pal tum comparisons reuse karna chahte ho, tum naive matching chhodkar KMP Algorithm ki taraf ja rahe ho.

Connections

Naive pattern matching — O(nm) — woh parent jise yeh bank drill karta hai.
KMP Algorithm — "har shift par $j = 0$ restart" ka fix.
Boyer-Moore Algorithm — worst case beat karne ke liye aage skip karta hai.
Rabin-Karp Algorithm — $O (1)$ expected compares ke liye windows hash karta hai.
Big-O Notation — yahan worst vs average ki language.
Sliding Window Technique — kyun naive $O (1)$ per slide nahi hai.
Substring Search Problem — umbrella problem.