Pagini recente » Cod sursa (job #570642) | Cod sursa (job #32577) | Cod sursa (job #1366667) | Cod sursa (job #2720077) | Cod sursa (job #1078029)
#include <fstream>
#include <string>
#include <vector>
using namespace std;
ifstream fin("abc2.in");
ofstream fout("abc2.out");
typedef unsigned int uint;
const int pow= 20;
const int mod= 6613;
vector <uint> v[mod];
bool check( uint x ) {
bool ch= 0;
for ( vector <uint>::iterator it= v[x%mod].begin(); it!=v[x%mod].end(); ++it ) {
if ( *it==x ) {
ch= 1;
break;
}
}
return ch;
}
int t[pow];
string s, c;
inline int charint( char ch ) {
int sol= 0;
if ( ch=='b' ) {
sol= 1;
} else if ( ch=='c' ) {
sol= 2;
}
return sol;
}
inline uint base3( string ch ) {
uint sol= 0;
for ( int i= 0; i<(int)ch.size(); ++i ) {
sol= sol*3+charint(ch[i]);
}
return sol;
}
int main( ) {
t[0]= 1;
for ( int i= 1; i<pow; ++i ) {
t[i]= t[i-1]*3;
}
fin>>s>>c;
int n= (int)s.size(), m= (int)c.size();
uint k= base3(c);
v[k%mod].push_back(k);
while ( !c.empty() ) {
c.clear();
fin>>c;
if ( c.empty() ) {
break;
}
k= base3(c);
if ( !check(k) ) {
v[k%mod].push_back(k);
}
}
k= 0;
for ( int i= 0; i<m; ++i ) {
k= k*3+charint(s[i]);
}
int sol= 0;
if ( check(k) ) {
++sol;
}
for ( int i= m; i<n; ++i ) {
k= (k-t[m-1]*charint(s[i-m]))*3+charint(s[i]);
if ( check(k) ) {
++sol;
}
}
fout<<sol<<"\n";
return 0;
}