Cod sursa(job #1754970)

Utilizator ghost24ghost ghost ghost24 Data 9 septembrie 2016 01:31:05
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.88 kb
#include<iostream>
#include<fstream>
#include<vector>
#include<string>
#define DX 2000009
using namespace std;
fstream fin("strmatch.in",ios::in),fout("strmatch.out",ios::out);
vector<int> v;
string x,y,aux;
int pre[DX];

void f();
void solv();

int main()
{
    int i,j;

    fin>>aux;x=' '+aux;
    fin>>aux;y=' '+aux;
    f();
    solv();
    fout<<v.size()<<"\n";
    for(i=0;i<min((int)v.size(),1000);i++) fout<<v[i]<<" ";
    fout<<"\n";
}
void solv()
{
    int i,poz=0;
    for(i=1;i<y.size();i++)
    {
        while(poz && x[poz+1]!=y[i]) poz=pre[poz];
        if(x[poz+1]==y[i]) poz++;
        //cout<<poz<<" "<<i<<"\n";
        if(poz==x.size()-1)
        {
            v.push_back(i-x.size()+1);
        }
    }
}
void f()
{
    int poz=0,i;
    for(i=2;i<x.size();i++)
    {
        while(poz && x[poz+1]!=x[i]) poz=pre[poz];
        if(x[poz+1]==x[i]) poz++;
        pre[i]=poz;
    }
}