KMP Algorithm - String Matching المتقدم

class KMPMatcher {
    // Build failure function (LPS - Longest Proper Prefix which is also Suffix)
    buildLPS(pattern) {
        const lps = [0];
        let len = 0;
        let i = 1;

        while (i < pattern.length) {
            if (pattern[i] === pattern[len]) {
                len++;
                lps[i] = len;
                i++;
            } else {
                if (len !== 0) {
                    len = lps[len - 1];
                } else {
                    lps[i] = 0;
                    i++;
                }
            }
        }

        return lps;
    }

    // Find all occurrences
    search(text, pattern) {
        if (!pattern) return [];

        const lps = this.buildLPS(pattern);
        const matches = [];
        let i = 0; // text index
        let j = 0; // pattern index

        while (i < text.length) {
            if (text[i] === pattern[j]) {
                i++;
                j++;
            }

            if (j === pattern.length) {
                matches.push(i - j);
                j = lps[j - 1];
            } else if (i < text.length && text[i] !== pattern[j]) {
                if (j !== 0) {
                    j = lps[j - 1];
                } else {
                    i++;
                }
            }
        }

        return matches;
    }

    // Find first occurrence
    findFirst(text, pattern) {
        const matches = this.search(text, pattern);
        return matches.length > 0 ? matches[0] : -1;
    }

    // Replace all occurrences
    replaceAll(text, pattern, replacement) {
        const matches = this.search(text, pattern);
        if (matches.length === 0) return text;

        let result = '';
        let lastIndex = 0;

        matches.forEach(matchIndex => {
            result += text.substring(lastIndex, matchIndex) + replacement;
            lastIndex = matchIndex + pattern.length;
        });

        result += text.substring(lastIndex);
        return result;
    }
}

// Usage
const matcher = new KMPMatcher();
const text = "ABABDABACDABABCABCAB";
const pattern = "ABABCABAB";

console.log(matcher.search(text, pattern)); // [10]
console.log(matcher.findFirst(text, "ABC")); // 7