KMP String Matching Algorithm

// Given 2 strings A and B, find the number of occurrences of A in B as a substring.

// Note:
// Solve using the KMP string matching algorithm. Do not use an inbuilt library

import java.io.*;
import java.util.*;

public class Main {

    public static int[] computeLPS(String A) {
        int n = A.length();
        int[] LPS = new int[n];

        for(int i = 1; i < n; i++) {
            int j = LPS[i - 1];

            while(j > 0 && A.charAt(i) != A.charAt(j)) {
                j = LPS[j - 1];
            }

            if(A.charAt(i) == A.charAt(j)) {
                j++;
            }

            LPS[i] = j;
        }

        return LPS;
    }

    public static int KMP(String A, String B) {
        int LPS[] = computeLPS(A);

        int n1 = A.length();
        int n2 = B.length();

        int res = 0;
        int j = 0;

        for(int i = 0; i < n2; i++) {
            while(j > 0 && (j == n1 || A.charAt(j) != B.charAt(i))) {
                j = LPS[j - 1];
            }

            if(A.charAt(j) == B.charAt(i)) {
                j++;
            }

            if(j == n1) res++;
        }

        return res;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();

        while(T-- > 0) {
            String A = sc.next();
            String B = sc.next();

            System.out.println(KMP(A, B));
        }

        sc.close();
    }
}