fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <string>
  4. #include <queue>
  5. #include <map>
  6.  
  7. using namespace std;
  8.  
  9. struct Node {
  10.     map<char, int> children;
  11.     int failure;
  12.     int output; // Index of the virus (or -1 if no output)
  13.     Node() : failure(0), output(-1) {}
  14. };
  15.  
  16. int main() {
  17.     int numRows, numCols, numViruses;
  18.     cin >> numRows >> numCols >> numViruses;
  19.  
  20.     vector<vector<char>> board(numRows, vector<char>(numCols));
  21.     for (int row = 0; row < numRows; ++row) {
  22.         for (int col = 0; col < numCols; ++col) {
  23.             cin >> board[row][col];
  24.         }
  25.     }
  26.  
  27.     vector<string> viruses(numViruses);
  28.     cin.ignore();
  29.     for (int i = 0; i < numViruses; ++i) {
  30.         getline(cin, viruses[i]);
  31.     }
  32.  
  33.     // 1. Build the Trie
  34.     vector<Node> trie;
  35.     trie.push_back(Node()); // Root node
  36.     int nodeCount = 1;
  37.  
  38.     for (int i = 0; i < numViruses; ++i) {
  39.         int currentNode = 0;
  40.         for (char c : viruses[i]) {
  41.             if (trie[currentNode].children.find(c) == trie[currentNode].children.end()) {
  42.                 trie.push_back(Node());
  43.                 trie[currentNode].children[c] = nodeCount++;
  44.             }
  45.             currentNode = trie[currentNode].children[c];
  46.         }
  47.         trie[currentNode].output = i; // Mark the end of the virus
  48.     }
  49.  
  50.     // 2. Build Failure Links (BFS)
  51.     queue<int> qNodes;
  52.     for (auto const& [character, childNode] : trie[0].children) {
  53.         qNodes.push(childNode);
  54.     }
  55.  
  56.     while (!qNodes.empty()) {
  57.         int currentNode = qNodes.front();
  58.         qNodes.pop();
  59.  
  60.         for (auto const& [character, childNode] : trie[currentNode].children) {
  61.             int nextNode = childNode;
  62.             int failureNode = trie[currentNode].failure;
  63.             while (trie[failureNode].children.find(character) == trie[failureNode].children.end() && failureNode != 0) {
  64.                 failureNode = trie[failureNode].failure;
  65.             }
  66.             if (trie[failureNode].children.find(character) != trie[failureNode].children.end()) {
  67.                 trie[nextNode].failure = trie[failureNode].children[character];
  68.             }
  69.             if (trie[nextNode].output == -1) {
  70.                 trie[nextNode].output = trie[trie[nextNode].failure].output;
  71.             }
  72.             qNodes.push(nextNode);
  73.         }
  74.     }
  75.  
  76.     // 3. Search in the Board
  77.     string result(numViruses, '0');
  78.     // Search horizontally
  79.     for (int row = 0; row < numRows; ++row) {
  80.         int currentNode = 0;
  81.         for (int col = 0; col < numCols; ++col) {
  82.             char c = board[row][col];
  83.             while (trie[currentNode].children.find(c) == trie[currentNode].children.end() && currentNode != 0) {
  84.                 currentNode = trie[currentNode].failure;
  85.             }
  86.             if (trie[currentNode].children.find(c) != trie[currentNode].children.end()) {
  87.                 currentNode = trie[currentNode].children[c];
  88.             }
  89.             if (trie[currentNode].output != -1) {
  90.                 result[trie[currentNode].output] = '1';
  91.             }
  92.         }
  93.     }
  94.  
  95.     // Search vertically
  96.     for (int col = 0; col < numCols; ++col) {
  97.         int currentNode = 0;
  98.         for (int row = 0; row < numRows; ++row) {
  99.             char c = board[row][col];
  100.             while (trie[currentNode].children.find(c) == trie[currentNode].children.end() && currentNode != 0) {
  101.                 currentNode = trie[currentNode].failure;
  102.             }
  103.             if (trie[currentNode].children.find(c) != trie[currentNode].children.end()) {
  104.                 currentNode = trie[currentNode].children[c];
  105.             }
  106.             if (trie[currentNode].output != -1) {
  107.                 result[trie[currentNode].output] = '1';
  108.             }
  109.         }
  110.     }
  111.  
  112.     cout << result << endl;
  113.  
  114.     return 0;
  115. }
Success #stdin #stdout 0.01s 5284KB
comments (?)
stdin
copy 
4 5 4
attnt
oboot
campc
ontes
tt
attn
xyc
aoco
stdout
copy 
1101
https://ideone.com/AiLebn
language:
C++14 (gcc 8.3)
created:
7 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!