Cod sursa(job #104271)

Utilizator SpiriSpiridon Alexandru Spiri Data 16 noiembrie 2007 00:21:04
Problema Abc2 Scor 0
Compilator cpp Status done
Runda Happy Coding 2007 Marime 1.25 kb
#include <fstream>
#include <map>
#include <vector>
using namespace std;

ifstream fin ("abc2.in");
ofstream fout ("abc2.out");

string p, t;
vector<int> pi;
int n, m;
int rez;
map<string,int> mp;

void Kmp();
void Prefix();

int main()
{
    fin >> t;
    t=" " + t;
    n = t.size()-1;
    pi.resize(n+1);
    
    while ( fin >> p )
    {
          m = p.size();
          if ( mp[p] == 0 )
          {
             mp[p] = 1;
             p = " " + p;
             Kmp();
          }
    }
    
    
    fout << rez;
    
    fout.close();
    fin.close();
    
    return 0;
}

void Kmp()
{
     Prefix();
     int q = 0;
     for ( int i = 1; i <= n; i++ )
     {
         while ( q > 0 && p[q+1] != t[i] )
         {
               q = pi[q];
         }
         if ( p[q+1] == t[i] ) q++;
         if ( q == m )
         {
              // tipereshte - modelul cu deplasamentu i-m 
              q = pi[q];
              rez++;
         }
     }
}

void Prefix()
{
     pi[1] = 0;
     int k = 0;
     for ( int q = 2; q <= m; q++ )
     {
         while ( k > 0 && p[k+1] != p[q] )
         {
               k = pi[k];
         }
         if ( p[k+1] == p[q] ) k++;
         pi[q] = k;
     }
}