Cod sursa(job #1070578)

Utilizator Daniel3717Aleca Daniel Adrian Daniel3717 Data 1 ianuarie 2014 16:06:19
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 0.87 kb
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
string a,b;
vector <int> r;
int pre[2000005],i,pos;
int main(void)
{
    ifstream f("strmatch.in");
    ofstream g("strmatch.out");
    f>>a;
    f>>b;
    pre[0]=-1;
    for (i=1;i<a.size();i++)
    {
        pos=pre[i-1];
        while ((pos>=0)&&(a[pos+1]!=a[i]))
            pos=pre[pos];
        if (a[pos+1]==a[i])
            pre[i]=pos+1;
        else
            pre[i]=-1;
    }
    pos=-1;
    for (i=0;i<b.size();i++)
    {
        while ((pos>=0)&&(a[pos+1]!=b[i]))
            pos=pre[pos];
        if (a[pos+1]==b[i])
            pos++;
        if (pos+1==a.size())
        {
            if (r.size()<1000)
                r.push_back((i+1)-a.size());
        }
    }
    g<<r.size()<<'\n';
    for (i=0;i<r.size();i++)
        g<<r[i]<<' ';
    return 0;
}