Cod sursa(job #1552518)

Utilizator vlady1997Vlad Bucur vlady1997 Data 18 decembrie 2015 11:04:17
Problema Potrivirea sirurilor Scor 18
Compilator cpp Status done
Runda Arhiva educationala Marime 0.91 kb
#include <cstdio>
#include <cstring>
using namespace std;
char a[2000001], b[2000001];
int phia[2000001], phib[2000001], m, n, nr=0;
int PHI ()
{
    int i, k; phia[1]=0;
    for (i=2; i<=m; i++)
    {
        k=phia[i-1];
        while (k>0 && a[i]!=a[k+1]) k=phia[k];
        if (a[i]==a[k+1]) phia[i]=k+1;
        else phia[i]=0;
    }

}
int main()
{
    int i, k;
    freopen("strmatch.in","r",stdin);
    freopen("strmatch.out","w",stdout);
    gets(a+1); m=strlen(a+1); a[m+1]=' ';
    gets(b+1); n=strlen(b+1);
    PHI();
    for (i=1; i<=n; i++)
    {
        k=phib[i-1];
        while (k>0 && b[i]!=a[k+1]) k=phia[k];
        if (b[i]==a[k+1]) phib[i]=k+1;
        else phib[i]=0;
        if (phib[i]==m) nr++;
    }
    printf("%d\n",nr); k=0;
    for (i=1; i<=n; i++)
    {
        if (phib[i]==m) printf("%d ",i-m);
        k++;
        if (k==1000) break;
    }
    return 0;
}