Cod sursa(job #2550720)

Utilizator norryna07Alexandru Norina norryna07 Data 19 februarie 2020 08:40:14
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.99 kb
#include <bits/stdc++.h>
#define N 2000005
using namespace std;

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

char t[N], p[N]; ///t - text, p - pattern
int a[N]; ///pozitiile fiecarei aparitii
int urm[N];
int n, m, k;

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)
    {
        while (q>0 && p[q]!=t[i])
            q=urm[q-1];
        if (p[q]==t[i]) q++;
        if (q==n)
        {
            a[++k]=i-n+1;
        }
    }
}

void Afisare()
{
    fout<<k<<'\n';
    if (k>1000) k=1000;
    for (int i=1; i<=k; ++i)
        fout<<a[i]<<' ';
    fout<<'\n';
    fout.close();
}

int main()
{
    fin.getline(p, N);
    fin.getline(t, N);
    fin.close();
    n=strlen(p);
    m=strlen(t);
    Prefix();
    KMP();
    Afisare();
    return 0;
}