Cod sursa(job #1207492)

Utilizator nicol.bolasNicol Bolas nicol.bolas Data 13 iulie 2014 10:54:15
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.91 kb
#include<cstdio>
#include<fstream>
#include<cstring>
using namespace std;
#define NMAX 2000004
ifstream f("strmatch.in");
ofstream g("strmatch.out");
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;
    f.getline(A+1,NMAX);
    f.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];
        }
    }
    g<<r<<"\n";
    r=min(r,1000);
    for (i=1;i<=r;++i)
        g<<st[i]<<" ";
    g<<"\n";
    return 0;
}