Exercises — Naive pattern matching — O(nm)

Letters count karo: $T=$ M-I-S-S-I-S-S-I-P-P-I mein $n=11$ hai; $P=$ I-S-S mein $m=3$ hai. Candidate shifts $0$ se $n-m=8$ tak run karte hain, isliye $==n-m+1=11-3+1=9==$ hain. Exactly itne hi kyun: agar $P$ $s=8$ se baad start hota toh use positions $9,10,11$ par characters chahiye hote — lekin $T$ index $10$ par khatam hota hai, isliye $P$ end se run off ho jaata (figure mein pink bracket). Positions $0\dots 8$ hi woh akele hain jahan saare $m=3$ characters abhi bhi $T$ ke andar fit hote hain.

$j$ $0$ se start hota hai aur har matched character par ek baar increment hota hai.

• Full match: loop sirf isliye ruka kyunki j < m false ho gayi, yaani $j$ poora $j=m$ tak climb kar gaya. Har character match hua.
• Failure: loop isliye ruka kyunki T[s+j] == P[j] false ho gayi jabki abhi bhi $j<m$ tha. Toh $j$ $m$ se neeche stuck hai — woh stuck value pehle mismatching character ki index hai. Yaad rakhne ki ek line: $j==m$ ⇒ report; $j<m$ ⇒ dead shift.

Shifts $s=0\dots 3$ (kyunki $n-m=3$). Figure ko top se bottom tak padhte hain:

• $s=0$: A=A, B=B, A=A → MATCH ✅
• $s=1$: B≠A → fail at $j=0$
• $s=2$: A=A, B=B, A=A → MATCH ✅
• $s=3$: B≠A → fail at $j=0$

Valid shifts: $s===0,2==$. Note karo ki do matches overlap karte hain — positions $0,1,2$ aur $2,3,4$ index $2$ share karte hain. Naive matching khushi se overlapping matches dhundhta hai kyunki woh har baar $j$ ko scratch se restart karta hai.

Comparisons per shift add up karo (figure mein coloured cells count karo — matches plus woh ek mismatch jo har row ko stop karti hai):

• $s=0$: 3 comparisons (saari match).
• $s=1$: 1 comparison (B≠A, immediately break).
• $s=2$: 3 comparisons.
• $s=3$: 1 comparison.

Total $=3+1+3+1===8==$ comparisons. $O(nm)$ bound ke comparison mein itne kam kyun? Bound $(n-m+1)m=4\cdot 3=12$ sirf ek upper limit hai. Break ne do shifts ko ek-ek comparison tak cut kar diya, isliye humne $8<12$ kiya.

Shifts $s=0\dots 2$, shape mein saare identical:

• $s=0$: A=A, A=A, A≠B → fail at $j=2$ (3 comps)
• $s=1$: A=A, A=A, A≠B → fail at $j=2$ (3 comps)
• $s=2$: A=A, A=A, A≠B → fail at $j=2$ (3 comps)

Valid shifts: none. Comparisons $=3+3+3===9==$. Har shift ki full $m$ cost kyun: pattern ke pehle do characters "AA" hamesha all-A text se match karte hain, isliye break last character "B" ke mismatch hone tak fire nahi ho sakti. Yeh miniature mein worst-case shape hai.

Number of shifts $=n-m+1=12-4+1=9$. Har shift teen A's match karta hai phir B par fail hota hai — poore $m=4$ comparisons each, break kabhi early fire nahi hoti. Total $=(n-m+1)\cdot m=9\cdot 4===36==$. Yeh exact max kyun hai: koi shift $m$ se zyada comparisons cost nahi kar sakta, aur yahan har shift woh ceiling hit karta hai, isliye sum upper bound ke barabar hai. Yahi precisely $\Theta (nm)$ ka matlab hai — bound achieve hota hai, sirf respect nahi kiya jaata.

Random text par, kya ek shift ke position $j$ par character match hoga, yeh $\frac{1}{2}$ probability ke saath ek coin flip hai (binary alphabet). Ek shift par comparisons ki number woh characters ki count hai jo first mismatch tak check hote hain — lekin yeh $m$ se zyada kabhi nahi ho sakti, kyunki pattern mein sirf $m$ characters hain.

Pehle, idealised (unbounded) estimate. Agar hum pretend karte ki pattern infinitely long hai, toh ek shift par comparison count $K$ satisfy karta $\mathrm{Pr}(K=k)=(\frac{1}{2}{)}^{k-1}\frac{1}{2}$, aur uska mean hota $E_{\infty }={\sum }_{k=1}^{\infty }k{\left(\frac{1}{2}\right)}^k.$ Yeh derive karna ki yeh $2$ equals karta hai: plain geometric series se start karo, kisi bhi $|x|<1$ ke liye valid, ${\sum }_{k=0}^{\infty }{x}^k=\frac{1}{1-x}.$ Dono sides ko $x$ ke respect mein differentiate karo (left par term-by-term): ${\sum }_{k=1}^{\infty }k{x}^{k-1}=\frac{1}{(1-x{)}^2}.$ Apni sum ki shape match karne ke liye dono sides ko $x$ se multiply karo: ${\sum }_{k=1}^{\infty }k{x}^k=\frac{x}{(1-x{)}^2}.$ $x=\frac{1}{2}$ set karo: $E_{\infty }=\frac{1/2}{(1-1/2{)}^2}=\frac{1/2}{1/4}===2==.$

Ab finite-$m$ correction (edge case). Ek real pattern count ko $m$ par stop karta hai: jab bhi pehle $m$ characters saare match karte hain (probability $(\frac{1}{2}{)}^m$), shift exactly $m$ comparisons par khatam hoti hai rather than continue karne ke. $m$ par tail truncate karne se exact finite mean milta hai $E_m={\sum }_{k=1}^{m}k{\left(\frac{1}{2}\right)}^k+m{\left(\frac{1}{2}\right)}^m.$ Pehla sum unbounded mean minus uski apni tail hai; truncation carry out karne par, yeh clean closed form par telescope karta hai $E_m=2-{\left(\frac{1}{2}\right)}^{m-1}.$ Extremes check karo: $m=1$ deta hai $E_1=2-1=1$ (ek guaranteed comparison — correct); $m=3$ deta hai $E_3=2-\frac{1}{4}=1.75$; aur jaise jaise $m\to \infty$, $E_m\to 2$, idealised value recover karta hai. Toh har finite $m$ ke liye true expected comparisons per shift strictly $2$ se below hai, $2$ se neeche se approach karta hai.

Bottom line: $\approx n$ shifts ke saath, expected total work $\le 2n=O(n)$ hai, $m$ se independent. Finite pattern ise sirf sasta banata hai, kabhi zyada nahi, isliye $O(n)$ conclusion safe hai. $m$ kyun disappear hota hai: mismatches almost immediately hoti hain, isliye inner loop $m$ reach karne se bahut pehle mar jaata hai. Dreaded factor $m$ sirf tab appear hota hai jab text aur pattern conspire karte hain (all-same characters).

• Naive worst case (exact): $(n-m+1)m=(10^6-10^3+1)\times 10^3===999001000==$ comparisons (approximately $10^9$).
• KMP: iska bound $O(n+m)$ hai, lekin yeh ek constant factor hide karta hai — KMP prefix function ke saath wापस loop fall back hone par same text character se zyada baar compare kar sakta hai, aur standard worst-case comparison bound approximately $2n$ text-character comparisons hai (plus prefix table build karne ke liye $O(m)$). Toh ek fair worst-case comparison estimate hai $2n+2m\approx 2\times 10^6+2\times 10^3===2002000==\text{comparisons.}$
• Ratio (naive ÷ KMP): $\frac{999001000}{2002000}\approx ==499==$ (roughly paanch-sau-guna). Gap kyun aur factor 2 kyun matter karta hai: naive har baar slide karne par already matched characters ko re-check karta hai — har shift mein $m$ tak. KMP ka prefix function use skip karne deta hai, har text character ko bounded number of times padhta hai (kabhi bhi $\sim 2$ se zyada nahi). Crude "$n+m$" figure use karna ratio ko approximately $2\times$ overstate karta; honest constant-aware estimate wahi hai jo humne yahan use kiya. Growth rates ki bajaye actual counts chahiye hone par constants kyun matter karte hain, dekhо Big-O Notation.

Change: report match at s ke baad, return s add karo. Agar koi match nahi, return $-1$.

FIRST-MATCH(T, P):
    n = len(T);  m = len(P)
    for s = 0 to n - m:
        j = 0
        while j < m and T[s+j] == P[j]:
            j = j + 1
        if j == m:
            return s          # stop at first hit
    return -1

Worst case jab pattern kabhi occur nahi karta: early return kabhi fire nahi hoti, isliye hum saare $n-m+1$ shifts scan karte hain, aur har shift mein $m$ comparisons tak cost ho sakti hai (jaise L2.3/L3.1 ki all-same-character shape mein). Exact worst-case count isliye poora product hai $(n-m+1)m,$ all-matches version ke identical. Concretely, agar $n=12,m=4$ toh yeh $(12-4+1)\cdot 4===36==$ comparisons hai — wahi $36$ jaise L3.1 mein. "First match" modification sirf tab help karta hai jab ek match early exist karta hai; jab pattern kabhi occur nahi karta toh yeh kuch nahi kharidta, aur count exactly $(n-m+1)m$ hai.

Comparison T[s+j] == P[j] ko lower(T[s+j]) == lower(P[j]) se replace karo, jahan lower(c) ek uppercase letter ko on the fly lowercase mein map karta hai.

        while j < m and lower(T[s+j]) == lower(P[j]):

Yeh kyun kaam karta hai aur sasta rehta hai: hum individual characters ko sirf comparison ke moment par transform karte hain, isliye text ki koi extra $O(n)$ copy nahi banti. Total extra cost har comparison par ek lower call hai — ek constant factor, isliye complexity $O(nm)$ par rehti hai.

Pehle comparison operator precisely define karo. $\mathrm{match}(t,p)$ woh test hai jo hum har position par record karte hain: $\mathrm{match}(t,p)=\{\begin{array}{ll}\text{true}& \text{if }p=\text{?}(\text{wildcard: any }t\text{ passes})\\ \text{true}& \text{if }t=p(\text{ordinary equality})\\ \text{false}& \text{otherwise.}\end{array}$ Pseudocode mein:

        while j < m and (P[j] == '?' or T[s+j] == P[j]):

Trace, shifts $s=0\dots 2$. Yahan "$\mathrm{match}$✓" ka matlab hai $\mathrm{match}(t,p)$ true return kiya; ek wildcard position hamesha true return karti hai:

• $s=0$, window "ABA": $\mathrm{match}(A,A)$✓, $\mathrm{match}(B,\text{?})$✓, $\mathrm{match}(A,A)$✓ → MATCH ✅
• $s=1$, window "BAC": $\mathrm{match}(B,A)$✗ → fail at $j=0$
• $s=2$, window "ACA": $\mathrm{match}(A,A)$✓, $\mathrm{match}(C,\text{?})$✓, $\mathrm{match}(A,A)$✓ → MATCH ✅

Match count $===2==$ ($s=0$ aur $s=2$ par). Wildcard complexity kyun nahi change karta: har $\mathrm{match}$ call abhi bhi $O(1)$ hai; humne sirf kya equal count hota hai woh widen kiya. Worst case $O(nm)$ rehta hai.

Optimization criterion (explicitly stated): hum $n$ minimize kar rahe hain subject to ${\max }_{1\le m\le n}(n-m+1)m>100$. Har $n$ ke liye hum pehle best $m$ choose karte hain, phir $n$ ko upar scan karte hain.

Fixed $n$ ke liye best $m$: function $f(m)=(n-m+1)m=-m^2+(n+1)m$ $m$ mein ek downward-opening parabola hai, vertex $m_{\text{opt}}=\frac{n+1}{2}$ par maximize hota hai. Toh worst possible pattern length text ka roughly half hai — yeh biggest product deta hai. Kyunki $m$ ek integer hona chahiye, $m_{\text{opt}}$ ko nearest integer par round karo, deta hai ${\max }_{1\le m\le n}(n-m+1)m=\lfloor \frac{(n+1{)}^2}{4}\rfloor .$

$n$ ko upar scan karo, hamesha best $m$ use karte hue, jab tak max pehli baar $100$ exceed nahi karta:

• $n=18$: $m_{\text{opt}}=9.5$, $m=9$ lo (ya $10$) → $(18-9+1)\cdot 9=90$. ($90\le 100$, enough nahi.)
• $n=19$: $m_{\text{opt}}=10$, $m=10$ lo → $(19-10+1)\cdot 10=100$. ($100$ equals $100$ — problem strictly greater maangta hai, toh abhi bhi enough nahi.)
• $n=20$: $m_{\text{opt}}=10.5$, $m=10$ lo (ya $11$) → $(20-10+1)\cdot 10===110==$. ($110>100$ ✓ — pehli baar bar clear kiya.)

Answer: smallest text length $n===20==$ hai, maximizing pattern length $m===10==$ ke saath achieve hota hai (equivalently $m=11$, parabola ki symmetry se, jo $(20-11+1)\cdot 11=110$ bhi deta hai), $110$ worst-case comparisons yield karta hai. $m\approx n/2$ kyun aur $m\approx n$ kyun nahi: ek huge pattern bahut kam shifts chhодता hai ($n-m+1$ tiny hota hai), jabki ek tiny pattern per shift kam cost karta hai ($m$ tiny hota hai). Product middle mein peak karta hai — yahi parabola ka vertex hai.

Setup. Text $T$ mein ek single pointer $c$ track karo — currently compare ho raha text character ka index, $c=s+j$. Saare comparisons ko do disjoint types mein split karo:

• Matching comparisons — wo jahan T[s+j] == P[j] true hai. Har ek $j$ advance karta hai aur isliye $c=s+j$ ko ek se advance karta hai.
• Mismatching comparisons — wo jahan woh false hai. Har ek ek shift end karta hai.

Matching comparisons bound karna. Yahan distinctness bite karta hai. Suppose ek shift $s$ ne ek block $P[0\dots j-1]$ ko $T[s\dots s+j-1]$ ke against match kiya aur phir mismatch kiya. Kyunki $P$ ke characters saare different hain, $P[1],P[2],\dots$ mein se koi bhi $P[0]$ ke barabar nahi; aur wo text block jo humne abhi match kiya woh tha $P[0\dots j-1]$. Isliye us already-matched block ke andar koi doosri jagah nahi hai jahan $P[0]$ line up ho sake. Agla shift jo possibly match kar sakta hai woh $s+j$ hai — algorithm ka agla successful match previous run ke stop hone ke text position par ya uske baad shuru hona chahiye. Consequently matching comparison se ever consume kiye gaye text positions ka set sirf aage move karta hai: poore run mein, har text index at most ek baar match hota hai. Yeh at most $n$ matching comparisons hai.

Mismatching comparisons bound karna. Har shift at most ek mismatch mein khatam hoti hai (loop pehle false test par break karta hai), aur $n-m+1\le n$ shifts hain. Isliye at most $n$ mismatching comparisons.

Sum karna. Total comparisons $\le \underset{\text{matches}}{\underbrace{n}}+\underset{\text{mismatches}}{\underbrace{n}}=2n$. Hence $T_{\text{distinct-}P}(n,m)\le 2n=O(n).■$ Intuition kyun matter karta hai: distinctness us overlap ko kill karta hai jo re-checking cause karta hai — exactly woh redundancy jo KMP generally remove karta hai. Distinct patterns ke liye, naive already essentially KMP-fast hai.