Cod sursa(job #2734351)

Utilizator valentinchipuc123Valentin Chipuc valentinchipuc123 Data 31 martie 2021 19:05:00
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.89 kb
#include <bits/stdc++.h>

using namespace std;

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

int n,m,pi[2000005],nr=0;
string a,b;

vector<int> sol;

void make_prefix()
{
    int poz=0;
    pi[1]=0;

    for(int i=2; i<=n; i++)
    {

        while( poz!=0&&a[poz+1]!=a[i] )
            poz=pi[poz];

        if( a[poz+1]==a[i] ) poz++;

        pi[i]=poz;
    }
}

int main()
{
    f>>a>>b;
    n=a.length();
    m=b.length();
    a=" "+a;
    b=" "+b;

    make_prefix();

    int poz=0;

    for(int i=1; i<=m; i++)
    {

        while( poz!=0&&a[poz+1]!=b[i] )
            poz=pi[poz];

        if( a[poz+1]==b[i] ) poz++;

        if(poz==n)
        {
            poz=pi[poz];
            nr++;

            if( nr<=1000 ) sol.push_back(i-n);
        }
    }

    g<<nr<<'\n';

    for(int i=0; i<sol.size(); i++) g<<sol[i]<<' ';
}