Cod sursa(job #1178274)

Utilizator gapdanPopescu George gapdan Data 26 aprilie 2014 14:46:03
Problema Potrivirea sirurilor Scor 80
Compilator cpp Status done
Runda Arhiva educationala Marime 1 kb
#include<fstream>
#include<cstring>
using namespace std;
int n,m;
int rez[2000000];
char T[2000000],P[2000000];
int nr,v[1001];
void prefix()
{
    int k,q;
    rez[1]=0;
    k=0;
    for (q=2;q<=m;++q)
    {
        while (k>0 && P[k+1]!=P[q]) k=rez[k];
        if (P[k+1]==P[q]) ++k;
        rez[q]=k;
    }
}
int main()
{
    int i;
    fstream f("strmatch.in",ios::in);
    fstream g("strmatch.out",ios::out);
    f.getline(P,2000001);
    f.getline(T,2000001);
    n=strlen(T);m=strlen(P);
    for (i=n-1;i>=0;--i) T[i+1]=T[i];
    for (i=m-1;i>=0;--i) P[i+1]=P[i];
    prefix();
    int q=0;
    for (i=1;i<=n;++i)
    {
        while (q>0 && P[q+1]!=T[i])
            q=rez[q];
        if (P[q+1]==T[i]) q=q+1;
        if (q==m)
        {
            q=rez[q];
            ++nr;
            if (nr<=1000) v[nr]=i-m;
        }
    }
    g<<nr<<'\n';
    if (nr>1000)
        for (i=1;i<=1000;++i) g<<v[i]<<' ';
    else for (i=1;i<=nr;++i) g<<v[i]<<' ';
    return 0;
}