Cod sursa(job #1225846)

Utilizator RaileanuCristian Raileanu Raileanu Data 3 septembrie 2014 19:56:33
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 0.96 kb
#include <fstream>
#include<stdio.h>
#include<string.h>

using namespace std;
#define MX 2000010
char a[MX],b[MX];
int pi[MX], k, i, n,m, ns, sol[1024] ;

int main()
{
   freopen("strmatch.in", "r", stdin);
    ofstream f2("strmatch.out");
    fgets(a, sizeof(a), stdin);
	fgets(b, sizeof(b), stdin);


    n=strlen(a)-1;
    m=strlen(b)-1;
    for (i=n; i>0; i--)
        a[i]=a[i-1];
    for (i=m; i>0; i--)
        b[i]=b[i-1];


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

    k=0;
    for (i=1; i<=m && ns<=1000; i++)
        {   while (k>0 && a[k+1]!=b[i] )
                k=pi[k];
            if (a[k+1]==b[i] )
                k++;
            if (k==n)
                sol[++ns]=i-n;
        }

    f2<<ns<<"\n";
    for (i=1; i<=ns; i++)
        f2<<sol[i]<<" ";

    f2.close();
    return 0;
}