Cod sursa(job #1648492)

Utilizator sorynsooSorin Soo sorynsoo Data 11 martie 2016 10:27:59
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.94 kb
#include <fstream>
#include <vector>
#include <string.h>
using namespace std;
ifstream cin("strmatch.in");
ofstream cout("strmatch.out");
#define MAXS 2000005

vector<int> rasp;
char a[MAXS], b[MAXS];
int pr[MAXS];
int i,na,nb,k,nrsol;

int main()
{
    cin.getline(a+1, MAXS); na = strlen(a+1);
    cin.getline(b+1, MAXS); nb = strlen(b+1);

    for(i=2; i<=na; i++)
    {
        while(k && a[k+1] != a[i])
            k = pr[k];

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

        pr[i] = k;
    }
    k=0;

    for(i=1; i<=nb; i++)
    {
        while(k && a[k+1] != b[i])
            k = pr[k];

        if(a[k+1] == b[i])
            k++;

        if(k==na)
        {
            k = pr[k];
            nrsol++;
            if(nrsol <= 1000)
                rasp.push_back( i-na );
        }
    }

    cout<<nrsol<<"\n";
    for(i=0; i<rasp.size(); i++)
        cout<<rasp[i]<<" ";

    return 0;
}