Cod sursa(job #3212269)

Utilizator maiaauUngureanu Maia maiaau Data 11 martie 2024 15:13:50
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.9 kb
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int,int>;
#define pb push_back

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

const int N = 2e6+5;

int main()
{  
    int p[N]; string A, B;

    fin >> A >> B;
    int n = A.size(), m = B.size(); 
    if (n > m) { fout << 0; return 0; }
    A = '*' + A; B = '#' + B;
    
    int k = 0;
    for (int i = 2; i <= n; i++){
        while (k && A[i] != A[k+1]) k = p[k];
        if (A[i] == A[k+1]) k++;
        p[i] = k;
    }

    k = 0; int t = 0; queue<int> q;
    for (int i = 1; i <= m; i++){
        while (k && A[k+1] != B[i]) k = p[k];
        if (A[k+1] == B[i]) k++;
        if (k == n){
            k = p[n]; t++;
            if (t <= 1000)
                q.push(i - n);
        }
    }

    fout << t << '\n';
    while (!q.empty()){
        fout << q.front() << ' ';
        q.pop();
    }
    return 0;
}