Cod sursa(job #1552507)

Utilizator danstefanDamian Dan Stefan danstefan Data 18 decembrie 2015 11:00:31
Problema Potrivirea sirurilor Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.82 kb
#include <bits/stdc++.h>
using namespace std;
int n,i,k,phi[2000010],p[1010],phii[2000010],m,nr;
char a[2000010],b[2000010];
int main()
{
    freopen("strmach.in","r",stdin);
    ofstream g ("strmach.out");
    gets(a+1);
    gets(b+1);
    phi[1]=0;
    m=strlen(a+1);
    for(i=2; i<=m; ++i)
    {
        k=phi[i-1];
        while(k>0&&a[i]!=a[k+1])k=phi[k];
        if(a[i]==a[k+1])phi[i]=k+1;
        else phi[i]=0;
    }
    a[m+1]='!';
    n=strlen(b+1);
    for(i=1; i<=n; ++i)
    {
        k=phii[i-1];
        while(b[i]!=a[k+1]&&k)k=phi[k];
        if(b[i]==a[k+1])phii[i]=k+1;
        else phii[i]=0;
        if(phii[i]==m)
        {
            ++nr;
            if(nr<=1000)p[nr]=i-m;
        }
    }
    g<<nr<<'\n';
    for(i=1; i<=min(nr,1000); ++i)
        g<<p[i]<<" ";
    return 0;
}