Cod sursa(job #2288901)

Utilizator AndreiD31Dragan Andrei AndreiD31 Data 24 noiembrie 2018 09:09:41
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.64 kb
#include <bits/stdc++.h>

using namespace std;

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


char c[2000010],a[2000010];
int i,k,n,m,nr,p[2000010],sol[2000010];
int main()
{
    f>>c+1;
    f>>a+1;

    n=strlen(c+1);
    m=strlen(a+1);



    for(i=2;i<=n;i++){
        for(;k!=0 && c[k+1]!=c[i];) k=p[k];
        if(c[k+1] == c[i])k++;
            p[i]=k;
    }

    k=0;

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

        for(;k!=0 && c[k+1]!=a[i];)k=p[k];
        if(c[k+1]==a[i])k++;
        if(k==n){nr++;if(nr<=1000)sol[nr]=i-n;}

    }

    g<<nr<<'\n';
    for(i=1;i<=nr;i++)
        g<<sol[i]<<" ";
    return 0;
}