Cod sursa(job #2058423)

Utilizator vancea.catalincatalin vancea.catalin Data 5 noiembrie 2017 17:09:53
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.83 kb
#include<iostream>
#include<fstream>
#include<string>
#include<vector>
#define DN 2000010
using namespace std;
fstream fin("strmatch.in",ios::in),fout("strmatch.out",ios::out);
string a,b;
vector<int> v;
int la,lb,pi[DN];
void f()
{
    int i,k=0;
    pi[0]=pi[1]=0;
    for(i=2;i<=la;i++)
    {
        while(k>0 && a[k+1]!=a[i])
            k=pi[k];
        if(a[k+1]==a[i]) k++;
        pi[i]=k;
    }
}
int main()
{
    int poz=0,r=0,i;
    fin>>a>>b;
    la=a.size();
    lb=b.size();
    a='0'+a;
    b='0'+b;

    f();
    for(i=1;i<=lb;i++)
    {
        while(poz>0 && a[poz+1]!=b[i]) poz=pi[poz];
        if(a[poz+1]==b[i]) poz++;
        if(poz==la)
        {
            r++;
            if(r<=1000) v.push_back(i-la);
            poz=pi[poz];
        }
    }
    fout<<r<<"\n";
    for(i=0;i<v.size();i++)
        fout<<v[i]<<" ";
}