Cod sursa(job #1202969)

Utilizator armandpredaPreda Armand armandpreda Data 30 iunie 2014 12:27:32
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.94 kb
#include <cstdio>
#include <cstring>
#define MAX 2000005

using namespace std;

char p[MAX],s[MAX];
int n,m,pi[MAX],sol[MAX],nrsol;
void prefix();
void kmp();
int main()
{
    freopen("strmatch.in","r",stdin);
    freopen("strmatch.out","w",stdout);
    int i;
    scanf("%s\n%s",p+1,s+1);
    kmp();
    printf("%d\n",nrsol);
    if(nrsol>1000)
        nrsol=1000;
    for(i=1;i<=nrsol;++i)
        printf("%d ",sol[i]);
    return 0;
}
void prefix()
{
    int k;
    pi[1]=0,k=0;
    for(int i=2;i<=m;++i)
    {
        while(k>0 and p[k+1]!=p[i])
            k=pi[k];
        if(p[k+1]==p[i])
            k++;
        pi[i]=k;
    }
}
void kmp()
{
    int q=0;
    n=strlen(s+1),m=strlen(p+1);
    prefix();
    for(int i=1;i<=n;++i)
    {
        while(q>0 and p[q+1]!=s[i])
            q=pi[q];
        if(p[q+1]==s[i])
            q++;
        if(q==m)
            nrsol++,sol[nrsol]=i-q,q=pi[q];
    }
}