Gaint and Sifat

4
axbyczd
abc
--> 0

abcabcabcabc
abc
--> 4
Vị trí: 0, 3, 6, 9

aabacbaabbaaz
aab
--> 2
Vị trí: 0, 6

aaaaaa
aa
--> 5
Vị trí: 0, 1, 2, 3, 4

B1: Nhập dữ liệu

B2: Loại bỏ kí tự space

B3: KMP để đếm số lần xuất hiện của s trong S

B4: Xuất kết quả

==================================
Code:

function KMPPreprocess(p):
    m = len(p)
    prefix = [0] * m
    i = 1
    j = 0
    while i < m:
        if p[i] == p[j]:
            j += 1
            prefix[i] = j
            i += 1
        else:
            if j != 0:
                j = prefix[j-1]
            else:
                prefix[i] = 0
                i+=1
    return prefix

function KMPSearch(t, p, prefix):
    n, m = len(t), len(p)
    i = j = 0
    res = 0
    while i < n:
        if t[i] == p[j]:
            i += 1
            j += 1
        if j == m:
            res += 1
            j = prefix[j - 1]
        elif i < n and t[i] != p[j]:
            if j != 0:
                j = prefix[j - 1]
            else:
                i += 1
    return res

function main:
  read(T)
  for tc = 1 to T:
    readLine(S)
    readLine(s)
    S.replace(' ', '');
    s.replace(' ', '');
		prefix = KMPPreprocess(s)
    answer = KMPSearch(S, s, prefix)
    print("Case " + tc + ": " + answer);

Độ phức tạp: O(T * (|S| + |s|))