Cod sursa(job #1674760)

Utilizator teodoramusatoiuTeodora Musatoiu teodoramusatoiu Data 4 aprilie 2016 20:45:21
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1 kb
#include <iostream>
#include <string.h>
#include <fstream>

using namespace std;
ifstream in ("strmatch.in");
ofstream out ("strmatch.out");

const int Max= 2000005;

char A[Max], B[Max];
int pref[Max];
int na,nb,num;
int rez[Max];

void calculprefixe()
{
    int k=0,i;
    for(i=2; i <= na; i++)
    {
        while(k>0 && A[k+1] != A[i])
            k = pref[k];
        if( A[k+1] == A[i] )
            k++;
        pref[i]=k;
    }
}

void rezult()
{
    int k=0;
    for(int i=1; i <= nb; i++)
    {
        while(k>0 && A[k+1] != B[i])
            k = pref[k];
        if(A[k+1] == B[i])
            k++;
        if(k == na)
        {
            num++;
            rez[num] = i - na + 1;
        }
    }
}

int main()
{
    in >> (A + 1) >> (B + 1);

    na = strlen( A+1 );
    nb = strlen( B+1 );

    if(na > nb)
    {
        out<<0;
        return 0;
    }

    calculprefixe();
    rezult();

    out<< num << '\n';

    for(int i=1; i<= min( num, 1000); i++)
        out<< rez[i] - 1 << " ";

    return 0;
}