Cod sursa(job #2663258)

Utilizator radu16012003Radu Dumitrache radu16012003 Data 25 octombrie 2020 18:40:30
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.04 kb
#include <fstream>

using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
#define Nrmax 2000001
char a[Nrmax],b[Nrmax];
int pi[Nrmax],n,m,nr,poz[Nrmax];
void make_prefix()
{
    int q=0;
    for (int i=2;i<=m;i++)
    {
        while (q && a[q+1]!=a[i])
            q=pi[q];
        if (a[q+1]==a[i])
            q++;
        pi[i]=q;
    }



}

int main()
{
    fin>>a;
    fin>>b;
    for (;a[m];m++);
    for (;b[n];n++);
    for (int i=m;i>=0;i--)
        a[i]=a[i-1];
    for (int i=n;i>=0;i--)
        b[i]=b[i-1];
    a[0]=b[0]=' ';
    //fout<<a<<'\n'<<b<<'\n';
    make_prefix();
    int q=0;
    for (int i=1;i<=n;i++)
    {
        while (q && a[q+1]!=b[i])
            q=pi[q];
        if (a[q+1]==b[i])
            q++;
        if (q==m)
        {
            q=pi[m];
            nr++;
            if (nr<=1000)
                poz[nr]=i-m;
        }
    }
    fout<<nr<<'\n';

    for (int i=1;i<=min(1000,nr);i++)
        fout<<poz[i]<<' ';

    return 0;
}