Cod sursa(job #2153937)

Utilizator ghiaradBadea Dragos ghiarad Data 6 martie 2018 16:27:42
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.94 kb
#include <bits/stdc++.h>

#define scooby_doo(a, b) ((a<b) ? a : b)
using namespace std;

ifstream f("strmatch.in");
ofstream g("strmatch.out");

string s;
string v;
int k,nr,pi[2000001],ns,nv,pos[1001];
void prefixe()
{
    int k=0;
    pi[1]=0;
    for(int i=2; i<=ns; ++i)
    {
        while(k && s[k+1] != s[i])k=pi[k];
        if(s[k+1]==s[i])++k;
        pi[i]=k;
    }
}

int main()
{
    getline(f,s);
    getline(f,v);
    ns=s.length();
    nv=v.length();
    for(int i=ns; i; --i)s[i]=s[i-1];
    s[0]=' ';
    for(int i=nv; i; --i)v[i]=v[i-1];
    v[0]=' ';
    prefixe();
    for(int i=1; i<=nv; ++i)
    {
        while(k && s[k+1] != v[i])k=pi[k];
        if(s[k+1] == v[i])++k;
        if(k==ns)
        {
            k=pi[ns];
            nr++;
            if(nr<=1000)pos[nr]=i-ns;
        }
    }
    g<<nr<<'\n';
    for(int i=1;i <= scooby_doo(nr, 1000); ++i)g<<pos[i]<<' ';
    return 0;
}