Cod sursa(job #2531147)

Utilizator StasBrega Stanislav Stas Data 25 ianuarie 2020 19:03:04
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.84 kb
#include <bits/stdc++.h>

using namespace std;

#define pb push_back

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

const int NMAX=2e6+5;
char a[NMAX],b[NMAX];
int p[NMAX],poz[1005],k,n,m;

int main()
{

    fin >> a >> b;
    n=strlen(a); m=strlen(b);

    int q=0;
    for(int i=1;i<n;i++)
    {
        while(q and a[q]!=a[i])
            q=p[q-1];
        if(a[i]==a[q])
            q++;
        p[i]=q;
    }
    q=0;
    for(int i=0;i<m;i++)
    {
        while(q and a[q]!=b[i])
            q=p[q-1];
        if(b[i]==a[q])
            q++;
        if(q==n)
        {
            q=p[n-1];
            k++;
            if(k<=1000)
                poz[k]=i-n+1;
        }
    }
    fout << k << "\n";
    for(int i=1;i<=min(k,1000);i++)
        fout << poz[i] << " ";

    return 0;

}