Cod sursa(job #1204394)

Utilizator Al3ks1002Alex Cociorva Al3ks1002 Data 2 iulie 2014 20:25:51
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.85 kb
// z-algo

#include<cstdio>
#include<fstream>
#include<algorithm>
#include<vector>
#include<bitset>
#include<deque>
#include<queue>
#include<set>
#include<map>
#include<cmath>
#include<cstring>
#include<ctime>
#include<cstdlib>

using namespace std;
const int nmax = 2000005;

int n,m,i,l,r,k,z[nmax],p[nmax],sol,S[nmax];
char a[nmax],b[nmax];

int main()
{
    freopen("strmatch.in","r",stdin);
    freopen("strmatch.out","w",stdout);

    scanf("%s",b+1);
    scanf("%s",a+1);

    n=strlen(a+1);
    m=strlen(b+1);

    // z[i] = lungimea celui mai lung prefix al lui b care incepe pe b[i]

    l=r=z[1]=0;
    for(i=2;i<=m;i++)
    {
        if(i>r)
        {
            l=i; r=i-1;
            while(r<m && b[r+1]==b[r-l+2]) r++;
            z[i]=r-l+1;
        }
        else
        {
            k=i-l+1;
            if(i+z[k]<=r)
            {
                z[i]=z[k];
            }
            else
            {
                l=i;
                while(r<m && b[r+1]==b[r-l+2]) r++;
                z[i]=r-l+1;
            }
        }
    }

    // p[i] = lungimea celui mai lung prefix a lui b care incepe pe a[i]

    l=r=0;
    for(i=1;i<=n;i++)
    {
        if(i>r)
        {
            l=i; r=i-1;
            while(r<n && a[r+1]==b[r-l+2]) r++;
            p[i]=r-l+1;
        }
        else
        {
            k=i-l+1;
            if(i+z[k]<=r)
            {
                p[i]=z[k];
            }
            else
            {
                l=i;
                while(r<n && a[r+1]==b[r-l+2]) r++;
                p[i]=r-l+1;
            }
        }
    }

    for(i=1;i<=n;i++)
    {
        if(p[i]==m)
        {
            sol++;
            if(sol<=1000) S[sol]=i-1;
        }
    }

    printf("%d\n",sol);
    for(i=1;i<=min(sol,1000);i++) printf("%d ",S[i]);

    return 0;
}