Cod sursa(job #2883965)

Utilizator valentinchipuc123Valentin Chipuc valentinchipuc123 Data 2 aprilie 2022 01:14:57
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.85 kb
#include <bits/stdc++.h>

using namespace std;

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

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

void automate()
{
    int i,poz=0;
    pi[1]=0;

    for(int i=2; i<=n; i++)
    {
        while(poz&&a[i]!=a[poz+1]) poz=pi[poz];
        if(a[poz+1]==a[i]) poz++;
        pi[i]=poz;
    }
}

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

    automate();

    int ct=0,poz=0;
    vector<int>elem;

    for(int i=1; i<=m; i++)
    {
        while( poz&&a[poz+1]!=b[i] ) poz=pi[poz];
        if(a[poz+1]==b[i]) poz++;

        if(poz==n)
        {
            poz=pi[poz];
            if(elem.size()<1000) elem.push_back(i-n);;
        }
    }

    g<<elem.size()<<'\n';
    for(int i=0; i<elem.size(); i++) g<<elem[i]<<' ';

    return 0;
}