Cod sursa(job #1290633)

Utilizator alex_bucevschiBucevschi Alexandru alex_bucevschi Data 11 decembrie 2014 16:52:44
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.84 kb
#include <bits/stdc++.h>

using namespace std;
char A[2000005],B[2000005];
int i,k,na,nb,pr[2000005],s[1010],sol;
inline void prefix()
{
    k=0;
    na=strlen(A+1);
    for(i=2;i<=na;i++)
    {
        while(k&&A[i]!=A[k+1])k=pr[k];
        if(A[i]==A[k+1])k++;
        pr[i]=k;
    }
}
inline void kmp()
{
    k=0;
    nb=strlen(B+1);
    for(i=1;i<=nb;i++)
    {
        while(k&&B[i]!=A[k+1])k=pr[k];
        if(B[i]==A[k+1])k++;
        if(k==na)
        {
            sol++;
            if(sol<=1000)
                s[sol]=i-na;
        }
    }
}
int main()
{
    freopen("strmatch.in","r",stdin);
    freopen("strmatch.out","w",stdout);
    scanf("%s%s",A+1,B+1);
    prefix();
    kmp();
    printf("%d\n",sol);
    sol=min(sol,1000);
    for(i=1;i<=sol;i++)
        printf("%d ",s[i]);
    return 0;
}