Cod sursa(job #3212273)

Utilizator maiaauUngureanu Maia maiaau Data 11 martie 2024 15:20:13
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.89 kb
#include <bits/stdc++.h>
using namespace std;
#define pb push_back

const int N = 2e6+5;

ifstream f("strmatch.in");
ofstream g("strmatch.out");

int n, m, t, p[N];
char a[N], b[N], aux[N];
vector<int> r;

int main()
{
    f >> a >> b;
    int n = strlen(a), m = strlen(b);
    strcat(aux, "#"); strcat(aux, a); strcpy(a, aux);
    strcpy(aux, "");
    strcat(aux, "*"); strcat(aux, b); strcpy(b, aux);
   
    if (n > m) {g << 0; return 0;}
    for (int i = 2; i <= n; i++){
        int k = p[i-1];
        while (k && a[i] != a[k+1]) k = p[k];
        if (a[i] == a[k+1]) k++;
        p[i] = k;
    }
    int k = 0;
    for (int i = 1; i <= m; i++){
        while (k && b[i] != a[k+1]) k = p[k];
        if (b[i] == a[k+1]) k++;
        if (k == n){
            t++; k = p[n];
            if (t <= 1000) r.pb(i-n);
        } 
    }
    g << t << '\n';
    for (auto it: r) g << it << ' ';

    return 0;
}