Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <map>
- #include <vector>
- #include <string>
- #include <array>
- #include <utility>
- #include <algorithm>
- const int N = 5;
- const char WILDCARD = '?';
- std::vector<std::string> patterns;
- std::array<char, N> alphabet = { 'A', 'C', 'T', 'G', 'N' };
- struct Node {
- std::map<char, Node*> son;
- std::map<char, Node*> go;
- Node* parent;
- Node* suffLink;
- Node* up;
- char charToParent;
- bool isTerminal;
- std::vector<int> leafPatternNumber;
- Node() {
- son = { {alphabet[0], NULL}, {alphabet[1], NULL}, {alphabet[2], NULL}, {alphabet[3], NULL}, {alphabet[4], NULL}, };
- go = { {alphabet[0], NULL}, {alphabet[1], NULL}, {alphabet[2], NULL}, {alphabet[3], NULL}, {alphabet[4], NULL}, };
- parent = nullptr;
- suffLink = nullptr;
- up = nullptr;
- charToParent = ' ';
- isTerminal = false;
- }
- };
- struct Trie {
- Node* root;
- Trie() {
- root = new Node();
- }
- Node* getSuffLink(Node* v) {
- if (v->suffLink == nullptr) {
- if (v == root || v->parent == root) {
- v->suffLink = root;
- } else {
- v->suffLink = getLink(getSuffLink(v->parent), v->charToParent);
- }
- }
- return v->suffLink;
- }
- Node* getLink(Node* v, char c) {
- if (v->go[c] == nullptr) {
- if (v->son[c]) {
- v->go[c] = v->son[c];
- } else if (v == root) {
- v->go[c] = root;
- } else {
- v->go[c] = getLink(getSuffLink(v), c);
- }
- }
- return v->go[c];
- }
- Node* getUp(Node* v) {
- if (v->up == nullptr) {
- if (getSuffLink(v)->isTerminal) {
- v->up = getSuffLink(v);
- } else if (getSuffLink(v) == root) {
- v->up = root;
- } else {
- v->up = getUp(getSuffLink(v));
- }
- }
- return v->up;
- }
- void addString(const std::string& s, int patternNumber) {
- Node* curr = root;
- for (char c : s) {
- if (curr->son[c] == nullptr) {
- curr->son[c] = new Node();
- curr->son[c]->parent = curr;
- curr->son[c]->charToParent = c;
- }
- curr = curr->son[c];
- }
- curr->isTerminal = true;
- curr->leafPatternNumber.push_back(patternNumber);
- }
- void processText(const std::string& text, std::vector<std::pair<int, int>>& results) {
- Node* curr = root;
- for (size_t i = 0; i < text.length(); ++i) {
- char c = text[i];
- curr = getLink(curr, c);
- Node* checkNode = curr;
- while (checkNode != root) {
- if (checkNode->isTerminal) {
- for (int patNum : checkNode->leafPatternNumber) {
- results.push_back({ i + 2 - patterns[patNum].length(), patNum + 1 });
- }
- }
- checkNode = getUp(checkNode);
- }
- }
- }
- };
- std::vector<int> findPatternWithWildcards(const std::string& text, const std::string& pattern, char wildcard) {
- std::vector<std::string> subPatterns;
- std::vector<int> startPositions;
- std::string currentSubPattern;
- for (size_t i = 0; i < pattern.length(); ++i) {
- if (pattern[i] == wildcard) {
- if (!currentSubPattern.empty()) {
- subPatterns.push_back(currentSubPattern);
- startPositions.push_back(i - currentSubPattern.length() + 1);
- currentSubPattern.clear();
- }
- } else {
- currentSubPattern += pattern[i];
- }
- }
- if (!currentSubPattern.empty()) {
- subPatterns.push_back(currentSubPattern);
- startPositions.push_back(pattern.length() - currentSubPattern.length() + 1);
- }
- Trie trie;
- for (size_t i = 0; i < subPatterns.size(); ++i) {
- trie.addString(subPatterns[i], i);
- }
- for (const auto& it : subPatterns) {
- patterns.push_back(it);
- }
- std::vector<std::pair<int, int>> results;
- trie.processText(text, results);
- std::vector<int> C(text.length(), 0);
- for (const auto& result : results) {
- int pos = result.first - startPositions[result.second - 1];
- if (pos >= 0 && pos + pattern.length() <= text.length()) {
- C[pos]++;
- }
- }
- std::vector<int> finalPositions;
- for (size_t i = 0; i < C.size(); ++i) {
- if (C[i] == subPatterns.size()) {
- finalPositions.push_back(i);
- }
- }
- // Фильтрация пересекающихся вхождений
- std::vector<int> nonOverlappingPositions;
- int lastEnd = -1;
- for (int pos : finalPositions) {
- if (pos > lastEnd) {
- nonOverlappingPositions.push_back(pos);
- lastEnd = pos + pattern.length() - 1;
- }
- }
- return nonOverlappingPositions;
- }
- int main() {
- std::string text;
- std::string pattern;
- char wildcard;
- std::cin >> text >> pattern >> wildcard;
- std::vector<int> positions = findPatternWithWildcards(text, pattern, wildcard);
- for (int pos : positions) {
- std::cout << pos << std::endl;
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement