Pagini recente » Cod sursa (job #2510751) | Cod sursa (job #1446231) | Cod sursa (job #2486770) | Cod sursa (job #870018) | Cod sursa (job #2555568)
#include <vector>
#include <cmath>
#include <cstdio>
#include <cstring>
using namespace std;
typedef unsigned int uint;
uint cv(char c){
return c-'a';
}
int n, m;
const uint c1 = 666013;
const uint alp = 3;
uint rm;
vector<uint> ve[c1];
struct roller{
uint val = 0;
void extend(char a){
val = (val*alp)+cv(a);
}
void roll(char a, char b){
val = (val - rm*cv(a))*alp + cv(b);
}
};
bool chek(uint val){
const vector<uint> &v = ve[val%c1];
for(auto a : v){
if(a == val){
return true;
}
}
return false;
}
void setz(uint val){
if(!chek(val)){
ve[val%c1].push_back(val);
}
}
FILE *fin, *fout;
char s[10000041], q[41];
void altoire(){
uint val = 0;
for(int i = 0; i < n; ++i){
val *= alp;
val += cv(q[i]);
}
setz(val);
}
int sol = 0;
void rezolvescu(){
roller r;
for(int i = 0; i < n; ++i){
r.extend(s[i]);
}
if(chek(r.val)){
sol++;
}
for(int i = n; i < m; ++i){
r.roll(s[i-n], s[i]);
if(chek(r.val)){
sol++;
}
}
printf("%d", sol);
}
int main(){
fin = freopen("abc2.in", "r", stdin);
fout = freopen("abc2.out", "w", stdout);
fgets(s, 10000041, fin);
m = strlen(s);
if(s[m-1] == '\n'){
m--;
}
while(fgets(q, 41, fin)){
if(n==0){
n = strlen(q);
if(q[n-1] == '\n'){
n--;
}
}
altoire();
}
rm = pow(alp, n-1);
rezolvescu();
return 0;
}