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;
- std::vector<std::string> patterns;
- std::array<char, N> alphabet = { 'A', 'C', 'G', 'T', '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() {
- parent = NULL;
- suffLink = NULL;
- up = NULL;
- charToParent = ' ';
- isTerminal = false;
- }
- };
- struct Trie {
- public:
- Node* root;
- Trie() {
- root = new Node();
- }
- Node* getSuffLink(Node* v) {
- if (v->suffLink == NULL) {
- 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] == NULL) {
- 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 == NULL) {
- 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) {
- std::cout << "/-----------------\\\n";
- std::cout << "Adding sample: " << s << "\n";
- Node* curr = root;
- for (char c : s) {
- std::cout << "current char: " << c << "\n";
- if (curr->son[c] == NULL) {
- curr->son[c] = new Node();
- curr->son[c]->parent = curr;
- curr->son[c]->charToParent = c;
- std::cout << "Adding new edge: " << (curr - root) << "{" << curr->charToParent << "} -> " << (curr->son[c] - root) << "{" << c << "}\n";
- }
- curr = curr->son[c];
- std::cout << "Current vertex: " << (curr - root) << "{" << c << "}\n";
- }
- curr->isTerminal = true;
- curr->leafPatternNumber.push_back(patternNumber);
- std::cout << "Vertex " << (curr - root) << "{" << curr->charToParent << "} marked final\n";
- std::cout << "Sample added " << s << "\n";
- std::cout << "\\-----------------/\n";
- }
- void check(Node* v, int i) {
- Node* u = v;
- while (u != root) {
- if (u->isTerminal) {
- for (int patNum : u->leafPatternNumber) {
- std::cout << "<!> Found match at position " << i - patterns[patNum].length() + 1 << " of pattern " << patterns[patNum] << "\n";
- }
- }
- u = getUp(u);
- }
- }
- void find_all_pos(std::string& t) {
- Node* u = root;
- for (size_t i = 0; i < t.length(); ++i) {
- std::cout << "STATE " << (u - root) << " INPUT " << t[i] << " AT POSITION " << i << "\n";
- std::cout << "/>=>=>=>=>=>=>=>=>\\\n";
- std::cout << "Getting advance from vertex " << (u - root) << "{" << u->charToParent << "} by char " << t[i] << "\n";
- u = getLink(u, t[i]);
- std::cout << "Advance from vertex " << (u - root) << "{" << u->charToParent << "} by char " << t[i] << " is " << (u - root) << "{" << t[i] << "}\n";
- std::cout << "\\>=>=>=>=>=>=>=>=>/\n";
- check(u, i + 1);
- }
- }
- void processText(std::string& s, std::vector<std::pair<int, int>>& ans) {
- std::cout << "Input string: " << s << "\n";
- Node* curr = root;
- for (size_t i = 0; i < s.length(); ++i) {
- char c = s[i];
- std::cout << "STATE " << (curr - root) << " INPUT " << c << " AT POSITION " << i << "\n";
- std::cout << "/>=>=>=>=>=>=>=>=>\\\n";
- std::cout << "Getting advance from vertex " << (curr - root) << "{" << curr->charToParent << "} by char " << c << "\n";
- curr = getLink(curr, c);
- std::cout << "Advance from vertex " << (curr - root) << "{" << curr->charToParent << "} by char " << c << " is " << (curr - root) << "{" << c << "}\n";
- std::cout << "\\>=>=>=>=>=>=>=>=>/\n";
- Node* checkNode = curr;
- while (checkNode != root) {
- std::cout << "Follow vertex " << (checkNode - root) << "{" << checkNode->charToParent << "} for matches\n";
- if (checkNode->isTerminal) {
- for (auto& patNum : checkNode->leafPatternNumber) {
- std::cout << "<!> Found match at position " << (i + 2 - patterns[patNum].length()) << " of pattern " << patterns[patNum] << "\n";
- ans.push_back(std::make_pair(i + 2 - patterns[patNum].length(), patNum + 1));
- }
- }
- std::cout << "/->->->->->->->->->\\\n";
- std::cout << "Getting follow suffix link for vertex " << (checkNode - root) << "{" << checkNode->charToParent << "}\n";
- checkNode = getUp(checkNode);
- std::cout << "Follow suffix link for vertex " << (checkNode - root) << "{" << checkNode->charToParent << "} is " << (checkNode - root) << "{" << checkNode->charToParent << "}\n";
- std::cout << "\\->->->->->->->->->/\n";
- }
- }
- }
- ~Trie() = default;
- } typedef Trie;
- int main() {
- Trie tr;
- std::string t;
- std::cin >> t;
- int n;
- std::cin >> n;
- for (size_t i = 0; i < n; ++i) {
- std::string str;
- std::cin >> str;
- patterns.push_back(str);
- }
- for (size_t i = 0; i < patterns.size(); ++i) {
- tr.addString(patterns[i], i);
- }
- std::vector<std::pair<int, int>> ans;
- tr.processText(t, ans);
- std::sort(ans.begin(), ans.end());
- for (const auto& it : ans) {
- std::cout << it.first << ' ' << it.second << '\n';
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement