Pagini recente » Cod sursa (job #828962) | Cod sursa (job #913533) | Cod sursa (job #1744506) | Cod sursa (job #823611) | Cod sursa (job #1078021)
#include <fstream>
#include <string>
#include <vector>
using namespace std;
ifstream fin("abc2.in");
ofstream fout("abc2.out");
typedef long long i64;
const int pow= 20;
const int mod= 6613;
vector <i64> v[mod];
int check( int x ) {
int ch= 0;
for ( vector <i64>::iterator it= v[x%mod].begin(); it!=v[x%mod].end(); ++it ) {
if ( *it==x ) {
ch= 1;
break;
}
}
return ch;
}
i64 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 i64 base3( string ch ) {
i64 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();
i64 k= base3(c);
v[k%mod].push_back(k);
while ( !c.empty() ) {
c.clear();
fin>>c;
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]);
}
i64 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;
}