Cod sursa(job #1879446)

Utilizator patrutoiuandreipatrutoiu andrei patrutoiuandrei Data 14 februarie 2017 21:45:54
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.91 kb
#include <fstream>
#include <string.h>

#define Ndim 2000001
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
int L[Ndim],SOL[1001];
char A[Ndim],B[Ndim];
int main()
{
    int i,k,n,m;
    fin>>(A+1)>>(B+1);
    n = strlen(A+1);
    m = strlen(B+1);
    k=0;
    for(i=2;i<=n;i++)
    {
        while(A[i] != A[k+1] && k>0)
        {
            k = L[k];
        }
        if(A[i] == A[k+1])
            k++;
        L[i] = k;
    }
    k=0;
    for(i=1;i<=m;i++)
    {
        while(B[i]!=A[k+1] && k > 0)
            k = L[k];
        if(B[i] == A[k+1])
            k++;
        if(k==n)
        {
            if(SOL[0]<1000)
                SOL[++SOL[0]] = i-k;
            else
                SOL[0]++;
            k = L[k];
        }

    }
    fout<<SOL[0]<<'\n';
    for(i=1;i<=min(1000,SOL[0]);i++)
        fout<<SOL[i]<<' ';
    return 0;
}