Cod sursa(job #2313052)

Utilizator ahriAhriixd ahri Data 5 ianuarie 2019 22:14:21
Problema Aho-Corasick Scor 90
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.17 kb
#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) {
    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 >> s;
    in >> n;

    for (int i = 1; i <= n; i++) {
        string word;
        in >> word;
        out << countStr(word) << "\n";
    }
    return 0;
}