Cod sursa(job #2056337)

Utilizator TudorFinaruTudor Cristian Finaru TudorFinaru Data 4 noiembrie 2017 11:06:07
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.99 kb
#include <fstream>
#include <string.h>

using namespace std;

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

#define NMax 2000005

int M, N,i,n ;
char A[NMax], B[NMax];
int q,pi[NMax], pos[2000004];



void prefix()
{
    int i, q = 0;
    for (i = 2, pi[1] = 0; i <= M; ++i)
    {
        while (q && A[q+1] != A[i]) q = pi[q];
        if (A[q+1] == A[i]) ++q;
        pi[i] = q;
    }
}



int main()
{
    fin.getline(A,NMax);
    fin.getline(B,NMax);
    M=strlen(A);
    N=strlen(B);

    for (i = M; i; --i) A[i] = A[i-1]; A[0] = ' ';
    for (i = N; i; --i) B[i] = B[i-1]; B[0] = ' ';

    prefix();

    for (i = 1; i <= N; ++i)
    {
        while (q && A[q+1] != B[i]) q = pi[q];
        if (A[q+1] == B[i]) ++q;
        if (q == M)
        { q = pi[M];
          ++n;
          pos[n] = i-M;
        }
    }

    fout<<n<<'\n';
    if(n>1000)n=1000;
    for (i = 1; i <= n;++i) fout<<pos[i]<<' ';
    fout<<'\n';


    return 0;
}