Cod sursa(job #1919319)

Utilizator caprariuapCaprariu Alin-Paul caprariuap Data 9 martie 2017 18:49:23
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.08 kb
#include <fstream>
#include <cstring>
#include <vector>
#include <algorithm>

using namespace std;

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

int n,m,i,j,urm[2000010],poz[1010],nr;
char a[2000010],b[2000010];

void prefix()
{
    int k,i;
    k=0;
    urm[1]=0;
    for (i=2; i<=n; i++)
    {
        while (k>0&&a[k+1]!=a[i])
            k=urm[k];
        if (a[k+1]==a[i])
            k++;
        urm[i]=k;
    }
}

void kmp()
{
    int q,i;
    q=0;
    for (i=1; i<=m; i++)
    {
        while (q>0&&a[q+1]!=b[i])
            q=urm[q];
        if (a[q+1]==b[i])
            q++;
        if (q==n)
        {
            q=urm[n];
            nr++;
            if (nr<=1000)
                poz[nr]=i-n;
        }
    }
}

int main()
{
    fin >> a >> b;
    n=strlen(a);
    m=strlen(b);
    for (i=n; i; i--)
        a[i]=a[i-1];
    for (i=m; i; i--)
        b[i]=b[i-1];
    prefix();
    kmp();
    fout << nr << '\n';
    nr=min(nr,1000);
    for (i=1; i<=nr; i++)
        fout << poz[i] << ' ';
    fout << '\n';
}