16

// Algo : KMP
char text[MAXN], pat[MAXN];
VI LPS(int m) {
    VI lps; lps.PB(0);
    int i = 1, j = 0;
    while (i < m) {
        if (pat[i] == pat[j]) {
            i++; j++;
            lps.PB(j);
        }
        else {
            if (j)
                j = lps[j-1];
            else {
                i++;
                lps.PB(0);
			}
        }
    }
    return lps;
}
// Count match
int GET_MIN_K(int n, int m) {
    VI lps = LPS(m);
    int i = 0, j = 0, counter = 0;
    while (i < n) {
        if (text[i] == pat[j]) {
            i++;
            j++;
        }
        if (j == m) {
            counter++;
            j = lps[j-1];
        }
        else if (i < n && text[i] != pat[j]) {
            if (j)
                j = lps[j-1];
            else
                i++;
        }
    }
    return counter;
}

Application :
1. Count total matching :  concate = pat + "$" + text
2. Smallest period      :  d = pat.length() - lps[pat.length()-1]
                           return (pat.length()%d == 0) ? d : len

// Algo : Z Algorithm

VI getZarr(string s) {        // Z অ্যারে তৈরি
 	int len = s.length();
 	VI zArr;
 	zArr.pb(0);
 	int left = 0, right = 0;
 	for (int k = 1; k < len; k++) {
 		if (k > right) {       // যদি বক্স তৈরি না হয়
 			left = right = k; // তাহলে left ও right একই জায়গা থেকে শুরু হবে
 			while (right < len && s[right] == s[right-left]) {
 				right++;      // যদি মিল পাওয়া যায়, তাহলে right index এর মান বাড়বে ।
 			}
 			zArr.pb(right - left);
 			right--;
 		}
 		else {
 			int k1 = k - left;
 			if (zArr[k1] <= right-k) {
 				zArr.pb(zArr[k1]);
 			}
 			else {
 				left = k;
 				while (right < len && s[right] == s[right-left]) {
 					right++;
 				}
 				zArr.pb(right);
 				right--;
 			}
 		}
 	}
 	return zArr;
 }