Cod sursa(job #1207491)

Utilizator nicol.bolasNicol Bolas nicol.bolas Data 13 iulie 2014 10:51:28
Problema Potrivirea sirurilor Scor 80
Compilator cpp Status done
Runda Arhiva educationala Marime 0.95 kb
#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
#define NMAX 2000004
int n,m,r,q,st[1005],p[NMAX+1];
char A[NMAX+1],B[NMAX+1];
void prefix()
{
    int i;
    q=0;
    for (i=2;i<=n;++i)
    {
        while (A[i]!=A[q+1] && q>0)
            q=p[q];
        if (A[i]==A[q+1])
            ++q;
        p[i]=q;
    }
}
int main()
{
    int i;
    freopen("strmatch.in","r",stdin);
    freopen("strmatch.out","w",stdout);
    cin.getline(A+1,NMAX);
    cin.getline(B+1,NMAX);
    n=strlen(A+1), m=strlen(B+1);
    prefix();
    q=0;
    for (i=1;i<=m;++i)
    {
        while (B[i]!=A[q+1] && q>0)
            q=p[q];
        if (B[i]==A[q+1])
            ++q;
        if (q==n)
        {
            ++r;
            if (r<1001) st[r]=i-n;
            q=p[q];
        }
    }
    printf("%d\n",r);
    r=min(r,1000);
    for (i=1;i<=r;++i)
        printf("%d ",st[i]);
    printf("\n");
    return 0;
}