Pagini recente » Monitorul de evaluare | Cod sursa (job #657945) | Cod sursa (job #3039940) | Monitorul de evaluare | Cod sursa (job #448071)
Cod sursa(job #448071)
#include<fstream>
#include<string>
using namespace std;
#define size(x) (int)x.size()
void read();
void write();
void make_prefix();
void doit();
string first, second;
int prefix[200], mx;
int main()
{
read();
make_prefix();
doit();
write();
return 0;
}
void read()
{
ifstream fin( "strmatch.in" );
fin >> first >> second;
fin.close();
}
void write()
{
ofstream fout( "strmatch.out" );
fout << mx;
fout.close();
}
void make_prefix()
{
int aux = 0;
for ( int i = 1; i < size( second ); ++i )
{
while ( aux && second[aux + 1] != second[i] )
aux = prefix[aux];
if ( second[aux + 1] == second[i] )
++aux;
prefix[i] = aux;
}
}
void doit()
{
int k = -1;
for ( int i = 0; i < size( first ); ++i )
{
if ( first[i] == second[k + 1] )
++k;
else
if ( k > -1 )
k = prefix[k];
if ( k == size( second ) - 1 )
{
++mx;
k = prefix[k];
}
}
}