Count Pattern Occurrences

**Tình huống.** Text s with |s| ≤ 1000000 and pattern p with |p| ≤ 100000, both over lowercase letters. Count how many times p occurs in s. **Thuật toán nào phù hợp nhất? Chương trình chỉ cần in ra chữ cái.** **A)** Check every starting position (|s|·|p| comparisons) **B)** KMP prefix function over p + '#' + s **C)** Digit DP over the string **D)** Kruskal on the characters