Cod sursa(job #2307642)

Utilizator PopeangaMihneaPopeanga Mihnea- Stefan PopeangaMihnea Data 25 decembrie 2018 11:40:29
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.92 kb
#include <bits/stdc++.h>

using namespace std;

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

const int L=2000001;
int sol[1001], pi[L+1];
char txt[L+1], pat[L+1];
int Nsol, n, m;

void prefix_function()
{
    int k=0;
    pi[1]=0;
    for(int q=2; q<=m; ++q)
    {
        while(k>0 && pat[k+1]!=pat[q]) k=pi[k];
        if(pat[k+1]==pat[q]) ++k;
        pi[q]=k;
    }
}

int main()
{
    fin.getline(pat+1, L);
    fin.getline(txt+1, L);
    m=strlen(pat+1);
    n=strlen(txt+1);

    prefix_function();

    int q=0;
    for(int i=1; i<=n; ++i)
    {
        while(q>0 && txt[i]!=pat[q+1]) q=pi[q];
        if(txt[i]==pat[q+1]) ++q;
        if(q==m)
        {
            q=pi[m];
            ++Nsol;
            if(Nsol<=1000) sol[Nsol]=i-m;
        }
    }

    fout<<Nsol<<"\n";
    for(int i=1; i<=min(1000, Nsol); ++i) fout<<sol[i]<<" ";
    fout<<"\n";
    return 0;
}