Cod sursa(job #1524852)

Utilizator dorin31Geman Dorin Andrei dorin31 Data 14 noiembrie 2015 15:00:08
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.97 kb
#include <iostream>
#include <fstream>
#include <cstring>
#define maxsize 2000100

using namespace std;

ifstream fin("strmatch.in");
ofstream fout("strmatch.out");

int urm[maxsize], sol[maxsize], n, m, nr;
char T[maxsize], P[maxsize];

void Prel(char *P)
{
    int x, k=0;
    urm[0]=0;
    for(x=2; x<=m; x++)
    {
        while(k>0 && P[k+1]!=P[x]) k=urm[k];
        if(P[k+1]==P[x]) k++;
        urm[x]=k;
    }
}
void KMP()
{
    int i, k=0;
    for(i=1; i<=n; i++)
    {
        while(k>0 && P[k+1]!=T[i]) k=urm[k];
        if(P[k+1]==T[i])k++;
        if(k==m)
        {
            ++nr;
            if (nr<1001) sol[nr]=i-m;
            k=urm[k];
        }
    }
}

int main()
{
    fin.getline(P+1,maxsize);
    fin.getline(T+1,maxsize);
    P[0]=T[0]='D';
    m=strlen(P)-1; n=strlen(T)-1;
    Prel(P);
    KMP();
    fout<<nr<<'\n';
    nr=min(1000,nr);
    for(int i=1; i<=nr; ++i)
        fout<<sol[i]<<' ';
    return 0;
}