Cod sursa(job #1280318)

Utilizator LegionHagiu Stefan Legion Data 1 decembrie 2014 19:38:08
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.04 kb
#include <iostream>
#include <fstream>
using namespace std;
int vtbl[2000001],rasp[1003],rasg=0;
string s,p;
ifstream in("strmatch.in");
void tabel()
{
    int x=-1,i;
    vtbl[0]=-1;
    for (i=1;i<p.length();i++)
    {
        while (x>-1&&p[x+1]!=p[i])
        {
            x=vtbl[x];
        }
        if (p[x+1]==p[i])
        {
            x++;
        }
        vtbl[i]=x;
    }
}
void rez()
{
    int x=-1,i;
    for (i=0;i<s.length();i++)
    {
        while (x>-1&&s[i]!=p[x+1])
        {
            x=vtbl[x];
        }
        if (s[i]==p[x+1])
        {
            x++;
            if (x==p.length()-1)
            {
                if (rasg<1001)
                rasp[rasg]=i-x;
                rasg++;
            }
        }
    }
}
void scrie()
{
    ofstream out("strmatch.out");
    out<<rasg<<"\n";
    int i;
    if (rasg>1001){rasg=1001;}
    for (i=0;i<rasg;i++)
    {
        out<<rasp[i]<<" ";
    }
}
int main()
{
    in>>p;
    in>>s;
    tabel();
    rez();
    scrie();
}