Pagini recente » Cod sursa (job #2531707) | Cod sursa (job #1711384) | Cod sursa (job #51103) | Cod sursa (job #876275) | Cod sursa (job #99118)
Cod sursa(job #99118)
#include <fstream>
#include <bitset>
#include <string>
#include <queue>
#define maxS 500000
using namespace std;
string A, B;
bitset <maxS> acc;
int sol, ns;
int trie[maxS][3], atm[maxS][3];
struct elem
{
int st;
int m;
int t;
};
queue <elem> Q;
void baga_trie()
{
int i, c, n, s = 0;
n = B.size();
for(i=0; i<n; ++i)
{
c = (int) B[i] - 'a';
if(!trie[s][c])
{
trie[s][c] = ++ ns;
s = ns;
}
else
s = trie[s][c];
}
acc[s] = 1;
}
void baga_atm(int t, int m, int nod)
{
int b, i;
b = atm[t][m];
atm[t][m] = trie[t][m];
if(acc[b]) acc[nod] = 1;
for(i=0; i<3; ++i)
if(trie[b][i]) atm[nod][i] = trie[b][i];
else atm[nod][i] = atm[b][i];
}
void bf()
{
int i, j;
elem x;
for(i=0; i<3; ++i)
if(trie[0][i])
{
x.st = 0;
x.m = i;
x.t = trie[0][i];
Q.push(x);
}
while(Q.empty() == false)
{
x = Q.front();
Q.pop();
baga_atm(x.st, x.m, x.t);
for(j=0; j<3; ++j)
if(trie[x.t][j])
{
elem nx;
nx.st = x.t;
nx.m = j;
nx.t = trie[x.t][j];
Q.push(nx);
}
}
}
int main()
{
ifstream fin("abc2.in");
ofstream fout("abc2.out");
fin >> A;
while(!fin.eof())
{
fin >> B;
baga_trie();
}
bf();
int i, s, n, c;
n = A.size();
s = 0;
for(i=0; i<n; ++i)
{
c = (int) A[i] - 'a';
s = atm[s][c];
if(acc[s]) ++ sol;
}
fout << sol;
fin.close();
fout.close();
return 0;
}