Pagini recente » Cod sursa (job #105181) | Cod sursa (job #341619) | Cod sursa (job #1690777) | Cod sursa (job #993599) | Cod sursa (job #1394066)
#include<fstream>
#include<cstring>
using namespace std;
typedef int var;
ifstream fin("ahocorasick.in");
ofstream fout("ahocorasick.out");
char STR[1000005];
char S[100005];
var PI[100005];
void build_pi() {
PI[0] = -1;
for(var i=1; S[i]; i++) {
var j = PI[i-1];
while(j != -1 && S[i] != S[j+1])
j = PI[j];
PI[i] = j+1;
}
}
var BAD[256];
void build_bad() {
var l = strlen(S);
fill(BAD, BAD+256, l);
for(var i=0; i<l-1; i++) {
BAD[S[i]-'a'] = l - i - 1;
}
}
int main() {
var n;
STR[0] = '#';
fin>>STR;
fin>>n;
while(n--) {
S[0] = '$';
fin>>S;
var size = strlen(S) - 1;
var j = 0;
var count = 0;
//build_pi();
build_bad();
for(var i=size; STR[i];) {
var j = size;
var k = i;
while(j>=0 && STR[k] ==S[j]) {
j --;
k --;
}
if(j < 0) {
count ++;
i++;
} else {
i = k + BAD[STR[k]-'a'];
}
}
fout<<count<<'\n';
}
return 0;
}