Cod sursa(job #2928599)

Utilizator DariusM17Murgoci Darius DariusM17 Data 23 octombrie 2022 14:39:54
Problema Potrivirea sirurilor Scor 38
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.78 kb
#include <bits/stdc++.h>
using namespace std ;
ifstream fin("strmatch.in") ;
ofstream fout("strmatch.out") ;
string s,pat ;
int urm[2000001] ;
vector <int> v ;
void makeprefix()
{
    int k=-1 ;
    urm[0]=0 ;
    for(int i=1; i<pat.size(); ++i)
    {
        while(k>0 && pat[i]!=pat[k+1]) k=urm[k] ;
        if(pat[i]==pat[k+1]) k++ ;
        urm[i]=k ;
    }
}
void KMP()
{
    int k=-1 ;
    for(int i=1; i<s.size(); ++i)
    {
        while(k>0 && pat[k+1]!=s[i]) k=urm[k] ;
        if(pat[k+1]==s[i]) k++ ;
        if(k==pat.size()-1) v.push_back(i-pat.size()+1) ;
    }
}
int main()
{
    fin>>pat>>s ;
    makeprefix() ;
    KMP() ;
    fout<<v.size()<<'\n' ;
    for(int i=0; i<min((int)v.size(),1000); ++i)
        fout<<v[i]<<" " ;

    return 0 ;
}