Cod sursa(job #3225438)

Utilizator maiaauUngureanu Maia maiaau Data 17 aprilie 2024 16:42:11
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.94 kb
#include <bits/stdc++.h>
using namespace std;
using pii = pair<int,int>;
#define pb push_back

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

const int N = 2000005;

int n, m, p[N]; 
string a, b;

int cnt;
queue<int> sol;

int main()
{
    fin.tie(0); fout.tie(0);
    ios_base::sync_with_stdio(0);
    fin >> a >> b; 
    n = a.size(); m = b.size();
    
    a = '*' + a; b = '*' + b;
    
    for (int i = 2; i <= n; i++){
        int pos = p[i-1];
        while (pos && a[pos+1] != a[i]) pos = p[pos];
        if (a[pos+1] == a[i]) pos++;
        p[i] = pos;
    }
    
    int pos = 0;
    for (int i = 1; i <= m; i++){
        while (pos && b[i] != a[pos+1]) pos = p[pos];
        if (b[i] == a[pos+1]) pos++;
        if (pos == n){
            cnt++; pos = p[pos];
            if (cnt <= 1000) sol.push(i - n);
        }
    }
    fout << cnt << '\n';
    while (!sol.empty()){ fout << sol.front() << ' '; sol.pop(); }
    
    return 0;
}