Cod sursa(job #2938356)

Utilizator DariusM17Murgoci Darius DariusM17 Data 11 noiembrie 2022 23:36:20
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.75 kb
#include <bits/stdc++.h>
using namespace std ;
ifstream fin("strmatch.in") ;
ofstream fout("strmatch.out") ;
#define NMAX 2000001
char a[NMAX],b[NMAX];
vector <int> v ;
int pi[NMAX],n,m;
void make_prefix()
{
    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) ;
    make_prefix() ;
    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) v.push_back(i-n) ;
    }
    fout<<v.size()<<'\n' ;
    for(int i=0; i<min(1000,(int)v.size()); ++i) fout<<v[i]<<" " ;

    return 0 ;
}