1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
|
#include <algorithm>
#include <cstdio>
#include <iostream>
#include <map>
#include <sstream>
#include <string>
#include <vector>
using std::cin;
using std::istringstream;
using std::map;
using std::string;
using std::vector;
// Preprocess the Burrows-Wheeler Transform bwt of some text
// and compute as a result:
// * starts - for each character C in bwt, starts[C] is the first position
// of this character in the sorted array of
// all characters of the text.
// * occ_count_before - for each character C in bwt and each position P in bwt,
// occ_count_before[C][P] is the number of occurrences of character C in bwt
// from position 0 to position P inclusive.
void PreprocessBWT(const string& bwt,
map<char, int>& starts,
map<char, vector<int> >& occ_count_before) {
// Implement this function yourself
}
// Compute the number of occurrences of string pattern in the text
// given only Burrows-Wheeler Transform bwt of the text and additional
// information we get from the preprocessing stage - starts and occ_counts_before.
int CountOccurrences(const string& pattern,
const string& bwt,
const map<char, int>& starts,
const map<char, vector<int> >& occ_count_before) {
// Implement this function yourself
return 0;
}
int main() {
string bwt;
cin >> bwt;
int pattern_count;
cin >> pattern_count;
// Start of each character in the sorted list of characters of bwt,
// see the description in the comment about function PreprocessBWT
map<char, int> starts;
// Occurrence counts for each character and each position in bwt,
// see the description in the comment about function PreprocessBWT
map<char, vector<int> > occ_count_before;
// Preprocess the BWT once to get starts and occ_count_before.
// For each pattern, we will then use these precomputed values and
// spend only O(|pattern|) to find all occurrences of the pattern
// in the text instead of O(|pattern| + |text|).
PreprocessBWT(bwt, starts, occ_count_before);
for (int pi = 0; pi < pattern_count; ++pi) {
string pattern;
cin >> pattern;
int occ_count = CountOccurrences(pattern, bwt, starts, occ_count_before);
printf("%d ", occ_count);
}
printf("\n");
return 0;
}
|
