Cod sursa(job #1769265)

Utilizator radu_uniculeu sunt radu radu_unicul Data 2 octombrie 2016 12:07:07
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.4 kb
#include<stdio.h>
using namespace std;

char A[2000005],B[2000005];
int LPS[2000005];
int sol[1000001];
int nrsol;
void lps()
{
    LPS[0]=0;
    int len=0;
    int i=0;
    int M=0;
    while(B[i])
    {
        M++;
        i++;
    }
    i=1;
    while(i<M)
    {
        if(B[i]==B[len])
        {
            len++;
            LPS[i]=len;
            i++;
        }
        else if(len!=0)
        {
            len=LPS[len-1];
        }
        else
        {
            LPS[i]=0;
            i++;
        }
    }
    //for(int i=0;i<M;i++) printf("%d ",LPS[i]);
}

void KMP()
{
    int i=0;
    int j=0;
    int N=0;
    int M=0;
    while(A[i])
    {
        N++;
        i++;
    }
    i=0;
    while(B[i])
    {
        M++;
        i++;
    }
    i=0;
    while(i<N)
    {
        if(A[i]==B[j])
        {
            i++;
            j++;
        }
        if(j==M)
        {
            sol[nrsol++]=i-j;
            j=LPS[j-1];
        }
        else if(i<N&&A[i]!=B[j])
        {
            if(j!=0) j=LPS[j-1];
            else i++;
        }
    }
}

int main()
{
    freopen("strmatch.in","r",stdin);
    freopen("strmatch.out","w",stdout);
    scanf("%s",&B);
    scanf("%s",&A);
    lps();
    KMP();
    if(nrsol>1000000) nrsol=1000000;
    printf("%d\n",nrsol);
    for(int i=0;i<nrsol;i++) printf("%d ",sol[i]);
}