Cod sursa(job #2682070)

Utilizator andrei.florea0405Florea Andrei-Bogdan andrei.florea0405 Data 7 decembrie 2020 18:50:41
Problema Potrivirea sirurilor Scor 20
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.23 kb
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define MOD 1000000007

typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef long long ll;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef double ld;

ifstream fin("strmatch.in");
ofstream fout("strmatch.out");

string a, b;
int pi[2000005];
vi sol;

void make_prefix() {
    pi[0] = 0;
    int q = 0;
    for (int i = 1; i < a.size(); i++) {
        while (q && a[q] != a[i])
            q = pi[q];
        
        if (a[q] == a[i])
            q++;
        
        pi[i] = q;
    }

}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    fin >> a >> b;

    make_prefix();
    int q = 0;
    int count = 0;
    for (int i = 0; i < b.size(); i++) {
        while (q && a[q] != b[i])
            q = pi[q];
        
        if (a[q] == b[i])
            q++;

        if (q == a.size()) {
            q = pi[a.size() - 1];
            count++;
            if (count <= 1000) {
                sol.pb(i - a.size() + 1);
            }
        }
    }
    
    fout << count << "\n";
    for (auto s : sol) {
        fout << s << " ";
    }
    fout << "\n";

    return 0;
}