Cod sursa(job #219786)

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

using namespace std;
int t[2000000],nr_sol=0;
string w,s;
queue <int> sol;

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(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);
    while(!sol.empty())
    {
      printf("%d ",sol.front());
      sol.pop();
    }
    fclose(stdout);
    return 0;
}