KMP Algorithm

1
#include <bits/stdc++.h>
2
using namespace std;
3
4
// Compute prefix function (pi) for string s
5
// pi[i] = length of the longest proper prefix of s
6
// that is also a suffix of s[0..i]
7
vector<int> prefix_function(const string &s) {
8
    int n = (int)s.size();
9
    vector<int> pi(n, 0);
10
    for (int i = 1; i < n; ++i) {
11
        int j = pi[i - 1];
12
        // Fallback using failure links until we can extend or reach 0
13
        while (j > 0 && s[i] != s[j]) j = pi[j - 1];
14
        if (s[i] == s[j]) ++j;
15
        pi[i] = j;
16
    }
17
    return pi;
18
}
19
20
// KMP search: return starting indices where pattern occurs in text
21
vector<int> kmp_search(const string &text, const string &pattern) {
22
    vector<int> res;
23
    if (pattern.empty()) return res; // define behavior: no matches for empty pattern
24
    vector<int> pi = prefix_function(pattern);
25
    int n = (int)text.size();
26
    int m = (int)pattern.size();
27
    int j = 0; // number of matched chars in pattern
28
    for (int i = 0; i < n; ++i) {
29
        while (j > 0 && text[i] != pattern[j]) j = pi[j - 1];
30
        if (text[i] == pattern[j]) ++j;
31
        if (j == m) {
32
            res.push_back(i - m + 1); // match ends at i
33
            j = pi[j - 1]; // allow overlapping matches
34
        }
35
    }
36
    return res;
37
}
38
39
int main() {
40
    ios::sync_with_stdio(false);
41
    cin.tie(nullptr);
42
43
    string text, pattern;
44
    // Example input: first the text line, then the pattern line
45
    if (!getline(cin, text)) return 0;
46
    if (!getline(cin, pattern)) return 0;
47
48
    vector<int> occ = kmp_search(text, pattern);
49
50
    cout << occ.size() << "\n";
51
    for (int i = 0; i < (int)occ.size(); ++i) {
52
        if (i) cout << ' ';
53
        cout << occ[i];
54
    }
55
    cout << "\n";
56
    return 0;
57
}
58

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
int main() {
17
    ios::sync_with_stdio(false);
18
    cin.tie(nullptr);
19
20
    string s;
21
    if (!(cin >> s)) return 0;
22
    int n = (int)s.size();
23
    vector<int> pi = prefix_function(s);
24
    int k = n - pi[n - 1]; // candidate minimal period
25
26
    if (n % k == 0) {
27
        cout << "minimal_period_length=" << k << ", repetitions=" << (n / k) << "\n";
28
    } else {
29
        cout << "minimal_period_length=" << n << ", repetitions=1\n";
30
    }
31
32
    // Bonus: list all border lengths by following pi links
33
    vector<int> borders;
34
    for (int L = pi[n - 1]; L > 0; L = pi[L - 1]) borders.push_back(L);
35
    sort(borders.begin(), borders.end());
36
    cout << "borders:";
37
    for (int L : borders) cout << ' ' << L;
38
    cout << "\n";
39
    return 0;
40
}
41

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
int main() {
17
    ios::sync_with_stdio(false);
18
    cin.tie(nullptr);
19
20
    string s;
21
    if (!(cin >> s)) return 0;
22
    int n = (int)s.size();
23
    vector<int> pi = prefix_function(s);
24
25
    // occ[len] = number of occurrences of prefix of length 'len' as a substring
26
    vector<int> occ(n + 1, 0);
27
28
    // Each prefix-function value pi[i] contributes one occurrence of that prefix as a suffix ending at i
29
    for (int i = 0; i < n; ++i) occ[pi[i]]++;
30
31
    // Propagate counts up the border chain: a longer prefix occurrence implies one occurrence of its borders
32
    for (int len = n; len > 0; --len) {
33
        if (len - 1 >= 0) occ[pi[len - 1]] += occ[len];
34
    }
35
36
    // Each prefix occurs at least once as itself (ending at its own index)
37
    for (int len = 1; len <= n; ++len) occ[len]++;
38
39
    // Output: for each prefix length, print its count
40
    for (int len = 1; len <= n; ++len) {
41
        cout << len << ": " << occ[len] << "\n";
42
    }
43
    return 0;
44
}
45

1
#include <bits/stdc++.h>
2
using namespace std;
3
4
struct KMPStream {
5
    string p;
6
    vector<int> pi;
7
    int j = 0;           // current matched length in pattern
8
    long long pos = 0;   // number of processed characters so far in the stream
9
10
    explicit KMPStream(string pattern) : p(std::move(pattern)) {
11
        int m = (int)p.size();
12
        pi.assign(m, 0);
13
        for (int i = 1; i < m; ++i) {
14
            int k = pi[i - 1];
15
            while (k > 0 && p[i] != p[k]) k = pi[k - 1];
16
            if (p[i] == p[k]) ++k;
17
            pi[i] = k;
18
        }
19
    }
20
21
    // Process a chunk and return starting indices (0-based) of matches in the global stream
22
    vector<long long> pushChunk(const string &chunk) {
23
        vector<long long> out;
24
        if (p.empty()) return out; // define: empty pattern -> no reports
25
        for (char c : chunk) {
26
            while (j > 0 && c != p[j]) j = pi[j - 1];
27
            if (c == p[j]) ++j;
28
            if (j == (int)p.size()) {
29
                long long start = (pos) - (long long)p.size() + 1; // match ends at current pos
30
                out.push_back(start);
31
                j = pi[j - 1];
32
            }
33
            ++pos;
34
        }
35
        return out;
36
    }
37
};
38
39
int main() {
40
    ios::sync_with_stdio(false);
41
    cin.tie(nullptr);
42
43
    string pattern; cin >> pattern;
44
    KMPStream kmp(pattern);
45
46
    int q; cin >> q; // number of chunks
47
    long long total = 0;
48
    while (q--) {
49
        string chunk; cin >> chunk;
50
        vector<long long> occ = kmp.pushChunk(chunk);
51
        total += (long long)occ.size();
52
        for (auto idx : occ) cout << idx << ' ';
53
    }
54
    cout << "\nTotal matches: " << total << "\n";
55
    return 0;
56
}
57