Cod sursa(job #2936957)

Utilizator xXoctavianXxStanescu Matei Octavian xXoctavianXx Data 9 noiembrie 2022 18:20:17
Problema Potrivirea sirurilor Scor 78
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.05 kb
#include <bits/stdc++.h>

using namespace std;

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

const int nmax=2e6+5;
int n,m,rasp;
char A[nmax],B[nmax];
int kmp[nmax];
int solutii[1003];

inline void indexFromOne()
{
    while(A[n]!=0) n++;
    while(B[m]!=0) m++;
    for(int i=n; i>0; i--) A[i]=A[i-1];
    A[0]=0;
    for(int i=m; i>0; i--) B[i]=B[i-1];
    B[0]=0;
}

inline void make_prefix()
{
    int q=0;
    kmp[1]=0;
    for(int i=2; i<=n; i++)
    {
        while(q && A[q+1] != A[i]) q=kmp[q];
        if(A[q+1] == A[i]) q++;
        kmp[i]=q;
    }
}

int main()
{
    fin>>A>>B;
    indexFromOne();
    make_prefix();

    int q=0;
    for(int i=2; i<=m; i++)
    {
        while(q && A[q+1] != B[i]) q=kmp[q];
        if(A[q+1] == B[i]) q++;
        if(q==n)
        {
            q=kmp[n];
            rasp++;
            if(rasp<=1000)
                solutii[rasp]=i-n;
        }
    }
    fout<<rasp<<"\n";
    for(int i=1; i<=min(rasp,1000); i++) fout<<solutii[i]<<" ";
    return 0;
}