String Operations, Memory Storage, and Pattern Matching Basics

Computer science me String characters ka ek contiguous sequence hota hai jo text representation ke liye use kiya jata hai. C language me string ko ek 1D character array ke roop me implement kiya jata hai jo ek special character Null Terminator ('\0', ASCII code 0) se terminate hota hai.

Memory Storage of Strings

Agar hum ek string char str[] = "HINGINEER"; store karte hain, toh memory me characters sequentially store hote hain aur compiler automatically end me '\0' append karta hai:

Index:      0     1     2     3     4     5     6     7     8     9
Character: [ H | I | N | G | I | N | E | E | R | \0 ]
Address:   2000  2001  2002  2003  2004  2005  2006  2007  2008  2009

Fundamental String Operations

1. Length Calculation (strlen): First character se start karke tab tak counter increment karte hain jab tak '\0' na mil jaye. Complexity: O(n).
2. Concatenation (strcat): First string ke null terminator par second string ke characters copy karna.
3. Comparison (strcmp): Do strings ke characters ko lexicographically (ASCII value ke hisaab se) compare karna.
4. Substring Extraction: Diye gaye starting index aur length ke according characters ko copy karna.

Brute Force Pattern Matching Algorithm

Diye gaye text T (length n) ke andar ek pattern P (length m) ko search karna Pattern Matching kehlata hai. Sabse intuitive technique Brute Force (Naive) Pattern Matching hoti hai:

NAIVE_STRING_MATCH(T, P)
1. n = length(T)
2. m = length(P)
3. For s = 0 to (n - m):
4.     j = 0
5.     While j < m and T[s + j] == P[j]:
6.         j = j + 1
7.     If j == m:
8.         Print "Pattern found at shift index: " s
9. End

Complexity of Naive Algorithm:

• Worst-case Time: O(m * (n - m + 1)) ya O(n * m). E.g. Text: "AAAAAAAAAB", Pattern: "AAB". Har position par almost saare characters match hote hain aur last me mismatch hota hai.
• Best-case Time: O(n) jab har shift par first character hi mismatch ho jaye.

Agli post me hum start karenge DSA Part-2: Searching & Sorting Algorithms, jisme pehla topic hoga Linear Search Algorithm and Complexity Analysis.