Cod sursa(job #2469623)

Utilizator bluestorm57Vasile T bluestorm57 Data 7 octombrie 2019 19:41:02
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.99 kb
//wish me luck
#include <bits/stdc++.h>

using namespace std;

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

const int NMAX = 2000005;
string A,B;
int n,m;
int pi[NMAX];
vector <int> ans;

void make_prefix(){
    int q = 0, i;
    pi[1] = 0;
    for(i = 2 ; i <= n ; i++){
        while(q && A[q + 1] != A[i])
            q = pi[q];
        if(A[q + 1] == A[i])
            q++;
        pi[i] = q;
    }
}

int main(){
    int i,q = 0,nr = 0;
    f >> A >> B;
    n = A.size();
    m = B.size();
    A = ' ' + A;
    B = ' ' + B;
    make_prefix();
    for(i = 1 ; i <= m ; i++){
        while(q && A[q + 1] != B[i])
            q = pi[q];
        if(A[q + 1] == B[i])
            q++;
        if(q == n){
            q = pi[n];
            if(ans.size() < 1000)
                ans.push_back(i - n);
            else
                nr++;
        }
    }
    g << ans.size() + nr << "\n";
    for(auto it: ans)
        g << it << " " ;

    return 0;
}