Cod sursa(job #1911753)

Utilizator Corneliu10Dumitru Corneliu Corneliu10 Data 7 martie 2017 21:43:33
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 0.95 kb
#include <iostream>
#include <fstream>
#include <cstring>
#define NMAX 2000010

using namespace std;

char A[NMAX],B[NMAX];
int pi[NMAX],pos[2000];

void prefix()
{
    int i,k = 0,n = strlen(A);
    pi[1] = k;
    for(i=2;i<=n;i++)
    {
        while(k && A[k+1]!=A[i])
            k = pi[k];

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

        pi[i]=k;
    }
}

int main()
{
    int i,nrpos=0;
    A[0] = B[0] = '0';
    ifstream f("strmatch.in");
    ofstream g("strmatch.out");

    f.getline(A+1,NMAX);
    f.getline(B+1,NMAX);
    int m = strlen(A);
    int n = strlen(B);

    prefix();
    int k = 0;
    for(i=1;i<=n;i++)
    {
        while(k && A[k+1]!=B[i])
            k = pi[k];

        if(A[k+1] == B[i])
            k++;

        if(k + 1==m)
        {
            k = pi[k];
            pos[nrpos++] = i - m + 1;
        }
    }
    g<<nrpos<<"\n";
    for(i=0;i<nrpos;i++)
        g<<pos[i]<<" ";
}