হ য ব র ল: Prefix Function (KMP)

Source : Link

Code :

Application :

1. KMP (Knuth-Morris-Pratt Algorithm) - একটা string T দেওয়া আছে এর মধ্যে string P এর সকল occurrence বের করতে হবে। তো আমরা একটা নতুন string create করবো S = P + "#" + T . তারপর S এর Prefix function থেকে আমরা এর occurrence গুলা পেয়ে যাব যেখানে pi[i] = n হবে (এখানে, n = size of P) .

2. সকল Prefix এর occurrence গণনা করতে হবে। ধরি, P একটা string, তো P[0...i] সকল prefix এর occurrence গণনা করতে হবে।

Let, P = aabaaab So, pi[] = 0 1 0 1 2 2 3.

আমরা cnt[pi[i]]++ করবো এবং cnt[i] যতবার আসছে তাতে (i-1) length এর prefix ও আছে, তাই আমরা cnt[pi[i-1]] += cnt[i] করবো, সবশেষে cnt[i]++ , যেহেতু original prefix ও যোগ করতে হবে।

So, cnt[] = 5 3 2 0 0 0 (1 - indexed). [ ith prefix occurs cnt[i] times]

vector<int> cnt(n + 1);
for (int i = 0; i < n; i++)
    cnt[pi[i]]++;
for (int i = n-1; i > 0; i--)
    cnt[pi[i-1]] += cnt[i];
for (int i = 1; i <= n; i++)
    cnt[i]++;

যদি P এর সকল prefix, T তে কতবার আছে তা বের করতে বলা হয় তবে S = P + "#" + T ধরে একই কাজ করবো। শুধু ১ম লুপটাতে i > n হবে (n = size of P) .

3. The number of different sub-string in a string - আমাদের এক্ষেত্রে জানা থাকবে যে শুরুতে string টিতে different sub-string কয়টা আছে। তারপর string টির শেষ এ নতুন character যোগ করে ঐ নতুন string এর different sub-string কয়টা পাবো তা বের করবো। তো এখানে character যোগ করার পর string টিকে reverse করে max(pi[i]) বের করতে হবে। তারপর নতুন sub-string পাবো = |S| + 1 - max(pi[i]). [S যোগ করার আগের string].

একই ভাবে string এর শুরুতে character যোগ / বাদ দিয়ে বা শেষে যোগ / বাদ দিয়ে নতুন স্ট্রিং এর different sub-string number বের করা যায় O(n) এ । m টা operation থাকলে O(nm) complexity হবে।

4. Compressing a string - একটা string S দেওয়া আছে এর থেকে একটা string T বানাতে হবে যত ছোট সম্ভব যাতে পাশাপাশি কয়েকটা T যোগ করলে S পাওয়া যায়। T হবে S এর prefix, তাই S এর prefix function বের করে n - pi[n-1] করলেই আমরা T এর length পেয়ে যাবো। ধরি এই T এর length = m, এখন যদি m divides n তো m আন্সার হবে নয়তো কোনো আন্সার নাই।