Cod sursa(job #2175257)

Utilizator crion1999Anitei cristi crion1999 Data 16 martie 2018 16:17:12
Problema Potrivirea sirurilor Scor 18
Compilator cpp Status done
Runda Arhiva educationala Marime 0.92 kb
#include <string.h>
#include <fstream>
#define NMAX 2000005

using namespace std;

int sol[NMAX];
char S[NMAX], P[NMAX], T[NMAX];
int nrsol = 0;
int n,m;
ifstream fi("strmatch.in");
ofstream fo("strmatch.out");

int main()
{

    fi>>(P+1);
    fi>>(S+1);
    n = strlen(P+1);
    m = strlen(S+1);
    int nrsol = 0;

    T[0] = T[1] = 0;

    int k = 0;
    for(int i = 2; i <= n; ++i)
    {
        while( k > 0 && P[k+1] != P[i])
            k = T[k];

        if(P[k+1] == P[i])
            k++;

        T[i] = k;

    }
    k = 0;

    for(int i = 1; i <= m; ++i)
    {
        while( k > 0 && P[k+1] != S[i])
            k = T[k];

        if(P[k+1] == S[i])
            k++;

        if(k == n)
        {
            k = T[k];
            sol[++nrsol] = i - n;

        }
    }
    fo<<nrsol<<'\n';
    for(int i = 1; i <= min(nrsol, 1000); ++i)
        fo<<sol[i]<<" ";
}