Cod sursa(job #1524777)

Utilizator dorin31Geman Dorin Andrei dorin31 Data 14 noiembrie 2015 13:55:51
Problema Potrivirea sirurilor Scor 14
Compilator cpp Status done
Runda Arhiva educationala Marime 1.05 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];

inline int minim(int a, int b) { return (a<b) ? a:b;}

void Urmatorul(char *P)
{
    int k=-1, x;
    urm[0]=0;
    for (x=1; 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 x=-1;
    for (int i=0; i<n; ++i)
    {
        while (x>0 && P[x+1]!=T[i]) x=urm[x];
        if (P[x+1]==T[i]) x++;
        if (x==m-1)
        {
            ++nr;
            if (nr<1001) sol[nr]=i-m+1;
            x=urm[x];
        }
    }
}

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