Cod sursa(job #2163324)

Utilizator caprariuapCaprariu Alin-Paul caprariuap Data 12 martie 2018 17:45:34
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.99 kb
#include <fstream>
#include <cstring>
#define nmax 2000010

using namespace std;

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

int pi[nmax],i,nr,ans[1010],n,m;
char a[nmax],b[nmax];

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

void kmp()
{
    int q=0;
    for (i=1; i<=m; i++)
    {
        while (q&&a[q+1]!=b[i])
            q=pi[q];
        if (a[q+1]==b[i])
            q++;
        if (q==n)
        {
            nr++;
            if (nr<=1000)
                ans[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';
    for (i=1; i<=min(nr,1000); i++)
        fout << ans[i] << ' ';
    fout << '\n';
}