Cod sursa(job #3242900)

Utilizator Cosmin2004_InfoMoldoveanu Cosmin Cosmin2004_Info Data 14 septembrie 2024 15:31:02
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1 kb
#include <bits/stdc++.h>

using namespace std;
const int N = 2e6 + 5;
string s;
int pi[N]; // cel mai lung sufix propriu egal cu un prefix
void kmp(string &s, int *pi) {
    int k = 0;
    for(int i = 1; i < s.length(); i++) {
        while(k > 0 && s[i] != s[k]) {
            k = pi[k - 1];
        }
        if(s[i] == s[k]) {
            k++;
        }
        pi[i] = k;
    }
}

// #define HOME

int main() {
#ifndef HOME
    ifstream cin("strmatch.in");
    ofstream cout("strmatch.out");
#endif
    string s, t;
    cin >> s >> t;
    kmp(s, pi);
    vector <int> ans;
    int k = 0;
    for(int i = 0; i < t.length(); i++) {
        while(k > 0 && t[i] != s[k]) {
            k = pi[k - 1];
        }
        if(t[i] == s[k]) {
            k++;
        }
        if(k == s.length()) {
            ans.push_back(i - s.length() + 1);
            k = pi[k - 1];
        }
    }
    cout << ans.size() << "\n";
    for(int i = 0; i < min((int)ans.size(), 1000); i++) {
        cout << ans[i] << " ";
    }
    return 0;
}