Cod sursa(job #2928583)

Utilizator DariusM17Murgoci Darius DariusM17 Data 23 octombrie 2022 14:01:25
Problema Potrivirea sirurilor Scor 38
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.93 kb
#include <bits/stdc++.h>
using namespace std ;
ifstream fin("strmatch.in") ;
ofstream fout("strmatch.out") ;
char s[2000001],pat[2000001] ;
int lps[2000001] ;
vector <int> v;
void makeprefix()
{
    int n=strlen(pat) ;
    lps[0]=0 ;
    int i=1,j=0 ;
    while(i<n)
    {
        if(pat[i]==pat[j])
            j++,lps[i]=j,i++ ;
        else
        {
            if(j) j=lps[j-1] ;
            else
                lps[i]=0,i++;
        }
    }
}
void KMP()
{
    int i=0,j=0,n=strlen(pat),m=strlen(s);
    while(m-i>=n-j)
    {
        if(pat[j]==s[i]) i++,j++ ;
        if(j==n) v.push_back(i-n);
        if(pat[j]!=s[i] && i<m)
        {
            if(j) j=lps[j-1] ;
            else i++ ;
        }

    }

}
int main()
{
    fin>>pat>>s ;
    makeprefix() ;
    KMP() ;
    fout<<v.size()<<'\n' ;
    for(int i=0; i<min(1000,(int)v.size()); ++i)
        fout<<v[i]<<" " ;

    return 0 ;
}