Cod sursa(job #2868751)

Utilizator rafaelrafyChitan Rafael rafaelrafy Data 11 martie 2022 10:07:11
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.92 kb
#include <iostream>
#include <fstream>
#include <cstring>
using namespace std;
int pi[2000010], sol[1010];
char a[2000010],b[2000010];
int n,m,N;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
void prefixare()
{
    int q=0;
    pi[1]=0;
    for(int i=2;i<=n;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+1>>b+1;

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

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

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

        if(q == n)
        {
            q = pi[q];
            N++;
            if(N<=1000)
                sol[N] = i;
        }
    }
    fout<<N<<'\n';
    for(int i=1;i<=N;i++)
        fout<<sol[i]-n<<' ';
    return 0;
}