Pagini recente » Cod sursa (job #2158786) | Cod sursa (job #2705677) | Cod sursa (job #1978074) | Cod sursa (job #2206680) | Cod sursa (job #98913)
Cod sursa(job #98913)
#include <fstream>
#include <string>
#include <set>
#define maxN 21
using namespace std;
string A, B;
set <string> M;
int sol;
int Next[maxN];
void prefix()
{
int i, q;
memset(Next, 0, sizeof(Next));
Next[0] = -1;
for(i=1, q=-1; i<B.size(); ++i)
{
while(B[i] != B[q+1] && q >= 0)
q = Next[q];
if(B[i] == B[q+1]) ++ q;
Next[i] = q;
}
}
int check()
{
int q, i, ret = 0;
for(i=0, q=-1; i<A.size(); ++i)
{
while(A[i] != B[q+1] && q >= 0)
q = Next[q];
if(A[i] == B[q+1])
++ q;
if(q == B.size()-1)
{
++ ret;
q = Next[q];
}
}
return ret;
}
int main()
{
ifstream fin("abc2.in");
ofstream fout("abc2.out");
fin >> A;
while(!fin.eof())
{
fin >> B;
if(M.find(B) == M.end())
{
M.insert(B);
prefix();
sol += check();
}
}
fout << sol;
fin.close();
fout.close();
return 0;
}