Cod sursa(job #2550718)

Utilizator JeomIlascu Beatrice Georgiana Jeom Data 19 februarie 2020 08:38:21
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.88 kb
#include <bits/stdc++.h>
#define N 2000005
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
char t[N],p[N];
int a[N],urm[N];///pozitiile in a
int n,m,k;

void citire()
{
    fin.getline(p,N);
    fin.getline(t,N);
    n=strlen(p);m=strlen(t);
    fin.close();
}
void prefix()
{
    int j=0;
    for(int i=1;i<n;++i)
    {
        while(j>0&&p[i]!=p[j])
            j=urm[j-1];
        if(p[i]==p[j]) j++;
        urm[i]=j;
    }
}
void kmp()
{
    int q=0;
    for(int i=0;i<m;++i)///in text
    {
        while(q>0&&p[q]!=t[i])
            q=urm[q-1];
        if(p[q]==t[i])q++;
        if(q==n)///tot paternul
            a[k++]=i-n+1;
    }
}
int main()
{
    citire();
    prefix();
    kmp();
    fout<<k<<'\n';
    if(k>1000) k=1000;
    for(int i=0;i<k;++i) fout<<a[i]<<' ';
    fout.close();
    return 0;
}