Last active
March 28, 2019 11:43
Revisions
-
iamcrypticcoder revised this gist
Mar 28, 2019 . 1 changed file with 69 additions and 43 deletions.There are no files selected for viewing
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode charactersOriginal file line number Diff line number Diff line change @@ -31,19 +31,19 @@ using namespace std; #define PB push_back #define SZ size() #define EPS 1e-9 #define SQR(x) ((x)*(x)) #define INF 2000000000 #define TO_DEG 57.29577951 #define PI 2*acos(0.0) #define ALL_BITS ((1 << 31) - 1) #define NEG_BITS(mask) (mask ^= ALL_BITS) #define TEST_BIT(mask, i) (mask & (1 << i)) #define ON_BIT(mask, i) (mask |= (1 << i)) #define OFF_BIT(mask, i) (mask &= NEG_BITS(1 << i)) #define IS_POWER_TWO(x) (x && !(x & (x-1))) #define OFF_RIGHTMOST_SET_BIT(x) (x & (x-1)) typedef long long LL; typedef unsigned long long ULL; @@ -81,93 +81,119 @@ inline int srcUInt() { uint ret; scanf("%u", &ret); return ret; } #define GRAY 1 #define BLACK 2 #define MAXN 1000 #define MAXS 500 #define MAXC 26 struct TrieNode { int parent; map<int, int> children; bool isKey; int failNode; vector<int> words; TrieNode() : parent(-1), isKey(false), failNode(0) {} TrieNode(int p) : parent(p), isKey(false), failNode(0) {} }; int root = 1; int nodes = 1; vector<TrieNode> trie(2); // Node 0 is unused bool result[MAXN + 7]; int charValue(char ch) { return ch - 'a'; } void insert(string const& key, int wordId) { int node = 1; for (int i = 0; i < key.length(); ++i) { int ch = charValue(key[i]); int &nextNode = trie[node].children[ch]; if (nextNode == 0) { nextNode = ++nodes; trie.push_back(TrieNode(node)); } node = nextNode; } trie[node].isKey = true; trie[node].words.push_back(wordId); } int findFailNode(int u, int ch) { int failNode = trie[u].failNode; while (failNode && !trie[failNode].children.count(ch)) failNode = trie[failNode].failNode; return failNode ? trie[failNode].children[ch] : root; } void bfs() { // Fail node for root is 0 trie[0].failNode = 0; queue<int> Q; Q.push(root); while (!Q.empty()) { int u = Q.front(); Q.pop(); map<int, int>::iterator it = trie[u].children.begin(); while (it != trie[u].children.end()) { int ch = it->first; int v = it->second; trie[v].failNode = findFailNode(u, ch); Q.push(v); it++; } } } int findNextNode(int node, int ch) { int answer = node; while (answer && !trie[answer].children.count(ch)) answer = trie[answer].failNode; return answer ? trie[answer].children[ch] : root; } void searchWords(string const& str) { int node = 1; for (int i = 0; i < str.length(); ++i) { int ch = charValue(str[i]); node = findNextNode(node, ch); for (int tmp = node; tmp != 0; tmp = trie[tmp].failNode) { FOR(k, 0, trie[tmp].words.size()-1) { //cout << trie[tmp].words[k] << " "; result[trie[tmp].words[k]] = true; } //cout << endl; } } } int main() { READ("input.txt"); //WRITE("input.txt"); int i, j; int TC, tc; double cl = clock(); string text; int N; getline(cin, text); N = srcInt(); getchar(); FOR(i, 0, N-1) { string word; getline(cin, word); insert(word, i); } bfs(); searchWords(text); FOR(i, 0, N-1) printf("%s\n", result[i] ? "Y" : "N"); cl = clock() - cl; fprintf(stderr, "Total Execution Time = %lf seconds\n", cl / CLOCKS_PER_SEC); return 0; } -
Mar 27, 2019 .There are no files selected for viewing
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode charactersOriginal file line number Diff line number Diff line change @@ -0,0 +1,173 @@ #include <set> #include <map> #include <list> #include <cmath> #include <ctime> #include <queue> #include <stack> #include <cctype> #include <cstdio> #include <string> #include <vector> #include <cassert> #include <cstdlib> #include <cstring> #include <sstream> #include <iostream> #include <algorithm> #include <unordered_set> using namespace std; #define FOR(i, L, U) for(int i=(int)L; i<=(int)U; i++) #define FORD(i, U, L) for(int i=(int)U; i>=(int)L; i--) #define READ(x) freopen(x, "r", stdin) #define WRITE(x) freopen(x, "w", stdout) #define ff first #define ss second #define PQ priority_queue #define PB push_back #define SZ size() #define EPS 1e-9 #define SQR(x) ((x)*(x)) #define INF 2000000000 #define TO_DEG 57.29577951 #define PI 2*acos(0.0) #define ALL_BITS ((1 << 31) - 1) #define NEG_BITS(mask) (mask ^= ALL_BITS) #define TEST_BIT(mask, i) (mask & (1 << i)) #define ON_BIT(mask, i) (mask |= (1 << i)) #define OFF_BIT(mask, i) (mask &= NEG_BITS(1 << i)) #define IS_POWER_TWO(x) (x && !(x & (x-1))) #define OFF_RIGHTMOST_SET_BIT(x) (x & (x-1)) typedef long long LL; typedef unsigned long long ULL; typedef pair<int, int> PII; typedef pair<uint, uint> PUU; typedef pair<double, double> PDD; typedef vector<bool> VB; typedef vector<int> VI; typedef vector<uint> VU; typedef vector<double> VD; typedef vector<char> VC; typedef vector<string> VS; typedef map<int, int> MII; typedef map<char, int> MCI; typedef map<string, int> MSI; typedef vector<vector<bool> > VVB; typedef vector<vector<int> > VVI; typedef vector<vector<double> > VVD; typedef vector<vector<PII> > VVPII; ULL GCD(ULL a, ULL b) { while (b)b ^= a ^= b ^= a %= b; return a; } // UP, RIGHT, DOWN, LEFT, UPPER-RIGHT, LOWER-RIGHT, LOWER-LEFT, UPPER-LEFT int dx[8] = { -1, 0, 1, 0, -1, 1, 1, -1 }; int dy[8] = { 0, 1, 0,-1, 1, 1, -1, -1 }; // Represents all moves of a knight in a chessboard int dxKnightMove[8] = { -1, -2, -2, -1, 1, 2, 2, 1 }; int dyKnightMove[8] = { 2, 1, -1, -2, -2, -1, 1, 2 }; inline int srcInt() { int ret; scanf("%d", &ret); return ret; } inline int srcUInt() { uint ret; scanf("%u", &ret); return ret; } #define WHITE 0 #define GRAY 1 #define BLACK 2 #define MAX 100000 #define MAXS 500 #define MAXC 26 struct TrieNode { int parent; map<char, int> children; bool isKey; int failNode; unordered_set<int> matches; TrieNode() : parent(-1), isKey(false), failNode(0) {} TrieNode(int p) : parent(p), isKey(false), failNode(0) {} }; vector<TrieNode> trie(1); int charValue(char ch) { return ch - 'a'; } void insert(string const& key, int wordId) { int node = 0; for (int i = 0; i < key.length(); ++i) { int ch = charValue(key[i]); int &nextNode = trie[node].children[ch]; if (nextNode == 0) { nextNode = trie.size(); trie.push_back(TrieNode(node)); } node = nextNode; } trie[node].matches.insert(wordId); } void bfs() { trie[0].failNode = 0; queue<int> Q; Q.push(0); while (!Q.empty()) { int u = Q.front(); Q.pop(); map<char, int>::iterator it = trie[u].children.begin(); while (it != trie[u].children.end()) { int ch = charValue(it->first); int v = it->second; int failNode = trie[u].failNode; while (failNode && !trie[failNode].children.count(ch)) failNode = trie[failNode].failNode; failNode = trie[failNode].children[ch]; trie[v].failNode = failNode; trie[v].matches.insert(trie[failNode].matches.begin(), trie[failNode].matches.end()); it++; } } } void searchWords(string const& str) { int node = 0; for (int i = 0; i < str.length(); ++i) { } } int main() { //READ("input.txt"); //WRITE("input.txt"); int i, j; int TC, tc; double cl = clock(); vector<string> keys; keys.PB("he"); keys.PB("she"); keys.PB("his"); keys.PB("hers"); string text = "ashishers"; searchWords(keys, text); cl = clock() - cl; fprintf(stderr, "Total Execution Time = %lf seconds\n", cl / CLOCKS_PER_SEC); return 0; }