Cod sursa(job #1119072)

Utilizator chiriacandrei25Chiriac Andrei chiriacandrei25 Data 24 februarie 2014 14:59:32
Problema Potrivirea sirurilor Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.98 kb
#include <cstdio>
#include <cstring>
#define Nmax 2000005

using namespace std;

int N,M,pi[Nmax],sol[Nmax];
char a[Nmax],b[Nmax];

inline void Pi()
{
    int i,k;
    pi[0]=-1; pi[1]=1;
    for(i=2;i<N;++i)
    {
        for(k=pi[i];k>=0 && a[k+1]!=a[i+1];k=pi[k]);
        if(k>=0 && a[k+1]==a[i+1])
        {
            if(k)
                pi[i+1]=pi[k]+1;
            else
                pi[i+1]=1;
        }
        else
            pi[i+1]=0;
    }
}

int main()
{
    int k=0,i;
    freopen ("strmatch.in","r",stdin);
    freopen ("strmatch.out","w",stdout);
    scanf("%s%s", (a+1),(b+1));
    N=strlen(a+1); M=strlen(b+1);
    Pi();
    for(i=1;i<=M;++i)
    {
        while(k>=0 && a[k+1]!=b[i])
            k=pi[k];
        if(k<0 || a[k+1]==b[i])
            ++k;
        if(k==N)
            sol[++sol[0]]=i-N;
    }
    printf("%d\n", sol[0]);
    for(i=1;i<=sol[0];++i)
        printf("%d ", sol[i]);
    printf("\n");
    return 0;
}