Cod sursa(job #1070580)

Utilizator Daniel3717Aleca Daniel Adrian Daniel3717 Data 1 ianuarie 2014 16:10:47
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.84 kb
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
string a,b;
vector <int> r;
int pre[2000005],i,pos,rs;
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())
                r.push_back((i+1)-a.size());
    }
    g<<r.size()<<'\n';
    rs=r.size();
    for (i=0;i<min(1000,rs);i++)
        g<<r[i]<<' ';
    return 0;
}