KMP - Prefix Function Applications

1
#include <bits/stdc++.h>
2
using namespace std;
3
4
// Compute prefix function (pi) for string s in O(n)
5
vector<int> prefix_function(const string &s) {
6
    int n = (int)s.size();
7
    vector<int> pi(n, 0);
8
    for (int i = 1; i < n; ++i) {
9
        int j = pi[i - 1];
10
        // Fallback along failure links until we can extend or reach 0
11
        while (j > 0 && s[i] != s[j]) j = pi[j - 1];
12
        if (s[i] == s[j]) ++j;
13
        pi[i] = j;
14
    }
15
    return pi;
16
}
17
18
int main() {
19
    ios::sync_with_stdio(false);
20
    cin.tie(nullptr);
21
22
    string s;
23
    // Example input: ababab
24
    if (!(cin >> s)) return 0;
25
26
    vector<int> pi = prefix_function(s);
27
    int n = (int)s.size();
28
    int T = n - (n ? pi[n - 1] : 0); // minimal period candidate
29
30
    // Check if s is periodic with period T
31
    bool periodic = (n > 0 && n % T == 0);
32
33
    cout << "String: " << s << "\n";
34
    cout << "pi: ";
35
    for (int x : pi) cout << x << ' ';
36
    cout << "\n";
37
38
    cout << "Minimal period length candidate T = n - pi[n-1] = " << T << "\n";
39
    if (periodic) {
40
        cout << "String is periodic. Minimal period = " << T << ", repeats = " << n / T << "\n";
41
        cout << "Period block: '" << s.substr(0, T) << "'\n";
42
    } else {
43
        cout << "String is not a repetition of a smaller block. Minimal period is the string itself (" << n << ")\n";
44
    }
45
46
    return 0;
47
}
48

1
#include <bits/stdc++.h>
2
using namespace std;
3
4
vector<int> prefix_function(const string &s) {
5
    int n = (int)s.size();
6
    vector<int> pi(n, 0);
7
    for (int i = 1; i < n; ++i) {
8
        int j = pi[i - 1];
9
        while (j > 0 && s[i] != s[j]) j = pi[j - 1];
10
        if (s[i] == s[j]) ++j;
11
        pi[i] = j;
12
    }
13
    return pi;
14
}
15
16
// KMP search: return starting indices where pattern occurs in text (including overlaps)
17
vector<int> kmp_search(const string &text, const string &pattern) {
18
    vector<int> res;
19
    int n = (int)text.size();
20
    int m = (int)pattern.size();
21
    if (m == 0) { // define: empty pattern matches at every position
22
        for (int i = 0; i <= n; ++i) res.push_back(i);
23
        return res;
24
    }
25
    vector<int> pi = prefix_function(pattern);
26
    int j = 0; // number of characters matched in pattern
27
    for (int i = 0; i < n; ++i) {
28
        while (j > 0 && text[i] != pattern[j]) j = pi[j - 1]; // fallback
29
        if (text[i] == pattern[j]) ++j; // extend
30
        if (j == m) {
31
            res.push_back(i - m + 1); // match ends at i
32
            j = pi[j - 1]; // allow overlaps by falling back
33
        }
34
    }
35
    return res;
36
}
37
38
int main() {
39
    ios::sync_with_stdio(false);
40
    cin.tie(nullptr);
41
42
    string text, pattern;
43
    // Example: text = ababababa, pattern = aba -> matches at 0,2,4,6
44
    if (!(cin >> text >> pattern)) return 0;
45
    vector<int> occ = kmp_search(text, pattern);
46
47
    cout << "Text:    " << text << "\n";
48
    cout << "Pattern: " << pattern << "\n";
49
    cout << "Count: " << occ.size() << "\n";
50
    cout << "Positions: ";
51
    for (int i = 0; i < (int)occ.size(); ++i) cout << occ[i] << (i + 1 == (int)occ.size() ? '\n' : ' ');
52
53
    return 0;
54
}
55

1
#include <bits/stdc++.h>
2
using namespace std;
3
4
vector<int> prefix_function(const string &s) {
5
    int n = (int)s.size();
6
    vector<int> pi(n, 0);
7
    for (int i = 1; i < n; ++i) {
8
        int j = pi[i - 1];
9
        while (j > 0 && s[i] != s[j]) j = pi[j - 1];
10
        if (s[i] == s[j]) ++j;
11
        pi[i] = j;
12
    }
13
    return pi;
14
}
15
16
// Given s, compute how many times each prefix s[0..v-1] appears as a substring of s.
17
// Returns vector occ of size n+1, occ[v] = count for prefix length v (occ[0] is unused = 0).
18
vector<long long> count_prefix_occurrences(const string &s) {
19
    int n = (int)s.size();
20
    vector<int> pi = prefix_function(s);
21
    vector<long long> occ(n + 1, 0);
22
23
    // Every position i contributes one occurrence to the border length pi[i]
24
    for (int i = 0; i < n; ++i) occ[pi[i]]++;
25
26
    // Propagate counts from longer borders to shorter via failure links
27
    // For v from n down to 1: add children counts to parent (pi[v-1])
28
    for (int v = n; v >= 1; --v) {
29
        if (v - 1 >= 0) occ[ (v - 1 >= 0 ? (v - 1 >= 0 ? (pi[v - 1]) : 0) : 0) ] += occ[v];
30
    }
31
32
    // Each prefix appears at least once as itself (ending at its own end)
33
    for (int v = 1; v <= n; ++v) occ[v]++;
34
35
    return occ;
36
}
37
38
int main() {
39
    ios::sync_with_stdio(false);
40
    cin.tie(nullptr);
41
42
    string s;
43
    // Example: s = ababa
44
    if (!(cin >> s)) return 0;
45
46
    auto occ = count_prefix_occurrences(s);
47
    cout << "String: " << s << "\n";
48
    cout << "Prefix occurrence counts (length -> count):\n";
49
    for (int v = 1; v <= (int)s.size(); ++v) {
50
        cout << v << " -> " << occ[v] << " (\"" << s.substr(0, v) << "\")\n";
51
    }
52
53
    return 0;
54
}
55

1
#include <bits/stdc++.h>
2
using namespace std;
3
4
vector<int> prefix_function(const string &s) {
5
    int n = (int)s.size();
6
    vector<int> pi(n, 0);
7
    for (int i = 1; i < n; ++i) {
8
        int j = pi[i - 1];
9
        while (j > 0 && s[i] != s[j]) j = pi[j - 1];
10
        if (s[i] == s[j]) ++j;
11
        pi[i] = j;
12
    }
13
    return pi;
14
}
15
16
// Build KMP automaton for lowercase 'a'..'z'.
17
// go[q][c] = next state from state q on character 'a'+c, states are 0..m.
18
vector<array<int,26>> build_kmp_automaton(const string &pat) {
19
    int m = (int)pat.size();
20
    vector<int> pi = prefix_function(pat);
21
    vector<array<int,26>> go(m + 1);
22
23
    for (int c = 0; c < 26; ++c) go[0][c] = 0;
24
    if (m > 0) go[0][pat[0]-'a'] = 1;
25
26
    for (int q = 1; q <= m; ++q) {
27
        for (int c = 0; c < 26; ++c) {
28
            if (q < m && pat[q] - 'a' == c) {
29
                go[q][c] = q + 1;
30
            } else {
31
                go[q][c] = go[ (q == 0 ? 0 : pi[q - 1]) ][c];
32
            }
33
        }
34
    }
35
    return go;
36
}
37
38
// Use automaton to count occurrences in a text quickly
39
int count_occurrences_automaton(const string &text, const string &pat, const vector<array<int,26>> &go) {
40
    int m = (int)pat.size();
41
    int state = 0, ans = 0;
42
    for (char ch : text) {
43
        if ('a' <= ch && ch <= 'z') {
44
            state = go[state][ch - 'a'];
45
            if (state == m) {
46
                ++ans;
47
                // Follow failure link implicitly via transition from state m
48
                // No manual fallback needed since go captures it
49
            }
50
        } else {
51
            // If the input can contain other chars, either extend alphabet or reset appropriately
52
            state = 0; // simple policy: reset on non-lowercase
53
        }
54
    }
55
    return ans;
56
}
57
58
int main() {
59
    ios::sync_with_stdio(false);
60
    cin.tie(nullptr);
61
62
    string pat;
63
    int T;
64
    // Example: pattern "aba", then multiple texts
65
    if (!(cin >> pat >> T)) return 0;
66
    auto go = build_kmp_automaton(pat);
67
68
    while (T--) {
69
        string text; cin >> text;
70
        int cnt = count_occurrences_automaton(text, pat, go);
71
        cout << cnt << "\n";
72
    }
73
74
    return 0;
75
}
76