Pagini recente » Cod sursa (job #1357782) | Cod sursa (job #648819) | Cod sursa (job #2475650) | Cod sursa (job #1028173) | Cod sursa (job #104271)
Cod sursa(job #104271)
#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;
}
}