Cod sursa(job #219781)

Utilizator brokensocialiconGrigoriu Cristian-Andrei brokensocialicon Data 8 noiembrie 2008 11:28:49
Problema Potrivirea sirurilor Scor 80
Compilator cpp Status done
Runda Arhiva educationala Marime 1.44 kb
#include <iostream>
#include <string>
#include <vector>

using namespace std;
int t[2000000],nr_sol=0;
string w,s;
vector <int> sol;
vector <int>::iterator it;

void citire()
{
    char buffer;
    freopen("strmatch.in","r",stdin);
    buffer=getc(stdin);
    while (buffer!='\n')
    {
        w+=buffer;
        buffer=getc(stdin);
    }

    buffer=getc(stdin);
    while (buffer!='\n')
    {
        s+=buffer;
        buffer=getc(stdin);
    }

    fclose(stdin);
}
void gen_table()
{
    int poz=2, cnd=0;
    t[0]=-1;
    t[1]=0;

    while (poz<w.length())
    {
        if (w[poz-1]==w[cnd])
        {
          t[poz]=cnd+1;
          poz++;
          cnd++;
        }
        else if (cnd>0)
          cnd=t[cnd];
        else
        {
          t[poz]=0;
          poz++;
        }

    }
}

void gaseste()
{
   int m=0,i=0;

 while (m+i<s.length())
 {
    if (w[i] == s[m+i])
    {
       i++;
       if (i == w.length())
       {
          if (nr_sol<1000)
             sol.push_back(m);
          nr_sol++;
          m++;
          i=0;
       }
    }
    else
    {
        m=m+i-t[i];
        if (i>0)
          i=t[i];
    }
 }
}
int main()
{
    citire();
    gen_table();
    gaseste();

    freopen("strmatch.out","w",stdout);
    printf("%d\n",nr_sol);
    for (it=sol.begin(); it!=sol.end();it++)
      printf("%d ",*it);
    fclose(stdout);
    return 0;
}