Pagini recente » Cod sursa (job #2926451) | Cod sursa (job #2378589) | Cod sursa (job #406580) | Cod sursa (job #601087) | Cod sursa (job #2313074)
#include <bits/stdc++.h>
using namespace std;
ifstream f("ahocorasick.in");
ofstream g("ahocorasick.out");
#define in f
#define out g
#define ascii (int)'a'
string s;
int n;
bool is_match(string& word, int index) {
int randomIdx = word.size() / 2;
if (word[randomIdx] != s[index + randomIdx]) {
return false;
}
for (int i = 0; i < word.size(); i++) {
if (word[i] != s[index + i]) {
return false;
}
}
return true;
}
int countStr(string& word) {
int table[26];
for(int i = 0; i < 26; i++) {
table[i] = word.size();
}
for (int i = 0; i < word.size(); i++) {
table[(int)word[i] - ascii] = word.size() - i - 1;
if(table[(int)word[i] - ascii] == 0) {
table[(int)word[i] - ascii] = 1;
}
}
int idx = 0;
int cnt = 0;
while (idx + word.size() <= s.size()) {
if (is_match(word, idx)) {
cnt++;
idx++;
} else {
idx += table[s[idx + word.size() - 1] - ascii];
}
}
return cnt;
}
int main() {
in.sync_with_stdio(false);
in.tie(0);
in >> s;
in >> n;
for (int i = 1; i <= n; i++) {
string word;
in >> word;
out << countStr(word) << "\n";
}
return 0;
}