Cod sursa(job #1911857)

Utilizator Corneliu10Dumitru Corneliu Corneliu10 Data 7 martie 2017 22:01:45
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.07 kb
#include <fstream>
#include <cstring>
#define inFile "strmatch.in"
#define outFile "strmatch.out"
#define maxA 2000010
using namespace std;

int pi[maxA],pos[1100],N;
char A[maxA],B[maxA];

void prefix(char B[])
{
    int i,k,l = strlen(B);

    pi[1] = 0;
    k = 0;

    for(i = 2;i < l;i++)
    {
        while(k > 0 && B[k + 1] != B[i])
            k = pi[k];
        if(B[k + 1] == B[i])
            k++;
        pi[i] = k;
    }
}

int main()
{
    int i,lA,q,lB;
    A[0] = B[0] = '0';

    ifstream f(inFile);
    ofstream g(outFile);

    f.getline(B + 1,maxA);
    f.getline(A + 1,maxA);

    prefix(B);
    lA = strlen(A);
    lB = strlen(B);
    q = 0;

    for(i=1;i<lA;i++)
    {
        while(q > 0 && A[i] != B[q + 1])
            q = pi[q];
        if(A[i] == B[q + 1])
            q++;
        if(q == lB - 1)
        {
            N++;
            if(N < 1002)
                pos[N] = i - lB + 1;
            q = pi[q];
        }
    }

    g<<N<<"\n";

    for(i=1;i<=min(N,1000);i++)
        g<<pos[i]<<" ";
}