Cod sursa(job #1571750)

Utilizator andreeainfo_dAndreea Dutulescu andreeainfo_d Data 18 ianuarie 2016 14:36:49
Problema Potrivirea sirurilor Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.94 kb
#include <cstdio>
#include <cstring>
using namespace std;
int phi1[2000005], phi2[2000005], n,m,i,k,nr,nr2;
char a[2000005], b[2000005];
void phi()
{
    int i,k;
    k=0;
    phi1[1]=0;
    for(i=2;i<=n;i++)
    {
        while(k>0&&a[k+1]!=a[i])
            k=phi1[k];
        if(a[k+1]==a[i])k++;
        phi1[i]=k;
    }
}
int main()
{
 //   freopen("strmatch.in","r",stdin);
   // freopen("strmatch.out","w",stdout);
    gets(a+1);
    gets(b+1);
    n=strlen(a+1);
    m=strlen(b+1);
    phi();
    k=0;
    for(i=1;i<=m;i++)
    {
        while(k>0&&a[k+1]!=b[i])
            k=phi1[k];
        if(a[k+1]==b[i])k++;
        phi2[i]=k;
    }
    for(i=1;i<=m;i++)
    {
        if(phi2[i]==n)nr++;
    }
    printf("%d\n",nr);
    for(i=n;i<=m;i++)
    {
        if(phi2[i]==n)
        {
            printf("%d ",i-n);
            nr2++;
            if(nr2==1000)break;
        }
    }
    return 0;
}