Cod sursa(job #1280258)

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