Cod sursa(job #1144558)

Utilizator alex_bucevschiBucevschi Alexandru alex_bucevschi Data 17 martie 2014 11:55:02
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.98 kb
#include <cstdio>
#include <cstring>
#define N 2000010
using namespace std;
char P[N],T[N];
int LP,LT,nr,i,k,pr[N],S[1005];
void prefix(),kmp();
int main()
{
    freopen("strmatch.in","r",stdin);
    freopen("strmatch.out","w",stdout);
    scanf("%s%s",P+1,T+1);
    LP=strlen(P+1);
    LT=strlen(T+1);
    prefix();
    kmp();
    printf("%d\n",nr);
    nr=nr>1000?1000:nr;
    for(i=1;i<=nr;i++)
        printf("%d ",S[i]);
    return 0;
}
void prefix()
{
    //se calculeaza functia prefix pentru patern P
    //pr[i]=cel mai lung sufix al prefixului P[1]P[2]....P[i] care este prefix propriu in P
    k=0;
    for(i=2;i<=LP;i++)
    {
        while(k&&P[i]!=P[k+1])k=pr[k];
        if(P[i]==P[k+1])k++;
        pr[i]=k;
    }
}
void kmp()
{
    k=0;
    for(i=1;i<=LT;i++)
    {
        while(k&&T[i]!=P[k+1])k=pr[k];
        if(T[i]==P[k+1])k++;
        if(k==LP)
        {
            nr++;
            if(nr<=1000)S[nr]=i-LP;
        }
    }
}