Cod sursa(job #1911776)

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

using namespace std;

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

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;m--;
    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==m)
        {
            k = pi[m];
            nrpos++;
            if(nrpos<=1000)
                pos[nrpos] = i - m;
        }
    }
    g<<nrpos<<"\n";
    for(i=1;i<=nrpos;i++)
        g<<pos[i]<<" ";
}