Cod sursa(job #1516878)

Utilizator sorynsooSorin Soo sorynsoo Data 3 noiembrie 2015 17:58:45
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 0.89 kb
#include <string.h>
#include <fstream>
#include <vector>
using namespace std;
ifstream cin("strmatch.in");
ofstream cout("strmatch.out");
#define maxsir 200000
char a[maxsir],b[maxsir];
int pr[maxsir],i,j,k,n,m,nrsol;
vector<int> rasp;
int main()
{
    cin.getline(a+1,maxsir); n=strlen(a+1);
    cin.getline(b+1,maxsir); m=strlen(b+1);

    for(i=2; i<=n; 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<=m; i++)
    {
        while(k && a[k+1]!=b[i])
            k=pr[k];

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

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

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