Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<bits/stdc++.h>
- using namespace std;
- void init(int N, char mString[]);
- void addWord(char mWord[]);
- void removeWord(char mWord[]);
- int correct(int mStart, int mEnd);
- void destory(char mResult[]);
- #define ADD_WORD 100
- #define REMOVE_WORD 200
- #define CORRECT 300
- #define MAX_LEN 40000
- #define MAX_WORD 10
- static char buf_s[MAX_WORD + 2];
- static char buf_b1[MAX_LEN + 2];
- static char buf_b2[MAX_LEN + 2];
- static int run() {
- int len;
- scanf("%d%s", &len, buf_b1);
- init(len, buf_b1);
- int cmdCount;
- scanf("%d", &cmdCount);
- int ret_val = 1;
- int ftype, start, end, ret, ans;
- for(int i = 0; i < cmdCount; i++) {
- scanf("%d", &ftype);
- switch(ftype) {
- case ADD_WORD:
- scanf("%s", buf_s);
- addWord(buf_s);
- break;
- case REMOVE_WORD:
- scanf("%s", buf_s);
- removeWord(buf_s);
- break;
- case CORRECT:
- scanf("%d %d", &start, &end);
- ret = correct(start, end);
- scanf("%d", &ans);
- if(ret != ans) {
- ret_val = 0;
- }
- break;
- }
- }
- for(int i = 0; i < len; i++) {
- buf_b2[i] = '\0';
- }
- destory(buf_b2);
- scanf("%s", buf_b1);
- for(int i = 0; i < len; i++) {
- if(buf_b1[i] != buf_b2[i]) {
- ret_val = 0;
- }
- }
- return ret_val;
- }
- int main()
- {
- int T, MARK;
- scanf("%d %d", &T, &MARK);
- for(int tc = 1; tc <= T; tc++) {
- if(run() == 1) {
- printf("#%d %d\n", tc, MARK);
- } else {
- printf("#%d 0\n", tc);
- }
- }
- return 0;
- }
- // Solutio starts here
- #define DEF vector<trieNode>(26, trieNode())
- struct trieNode {
- int next, tot;
- trieNode(): next(0), tot(0) {}
- };
- vector<vector<trieNode>> trie;
- vector<bool> endWord;
- int cur;
- string words;
- void add(string s) {
- int val = 1, x;
- for(int i = 0; i < s.length(); i++) {
- x = s[i] - 'a';
- if(trie[val][x].next == 0) {
- trie.push_back(DEF);
- endWord.push_back(false);
- trie[val][x].next = ++cur;
- }
- trie[val][x].tot += 1;
- val = trie[val][x].next;
- }
- // cerr << s << " " << val << endl;
- endWord[val] = true;
- }
- void rem(string s) {
- int val = 1, x;
- for(int i = 0; i < s.length(); i++) {
- x = s[i] - 'a';
- trie[val][x].tot -= 1;
- val = trie[val][x].next;
- }
- endWord[val] = false;
- }
- bool find(string s) {
- int val = 1, x;
- for(int i = 0; i < s.length(); i++) {
- x = s[i] - 'a';
- if(trie[val][x].tot == 0) {
- return false;
- }
- val = trie[val][x].next;
- }
- return endWord[val];
- }
- bool search(string& s, string& tmp, int val=1, bool f=false) {
- if(val == 0) {
- return 0;
- }
- if(s.length() == tmp.length()) {
- return endWord[val];
- }
- // cerr << "word = " << s << " " << tmp << " " << val << " " << f << endl;
- int i = tmp.length();
- int x = s[i] - 'a';
- if(f) {
- tmp += s[i];
- if(trie[val][x].tot != 0 && search(s, tmp, trie[val][x].next, f)) {
- return 1;
- }
- tmp.pop_back();
- } else {
- for(int z = 0; z < 26; z++) {
- tmp += (char)('a' + z);
- // cerr << x << " " << tmp << " " << z << endl;
- if(trie[val][z].tot != 0 && search(s, tmp, trie[val][z].next, (z != x))) {
- return 1;
- }
- tmp.pop_back();
- }
- }
- return 0;
- }
- void init(int N, char mString[]) {
- trie.clear();
- endWord.clear();
- cur = 1;
- trie.push_back(DEF);
- endWord.push_back(false);
- trie.push_back(DEF);
- endWord.push_back(false);
- string tmpWord(mString);
- words = tmpWord;
- }
- void addWord(char mWord[]) {
- string tmpWord(mWord);
- // cerr << "adding word = " << tmpWord << endl;
- add(tmpWord);
- // cerr << "word added\n";
- }
- void removeWord(char mWord[]) {
- string tmpWord(mWord);
- // cerr << "deleting word = " << tmpWord << endl;
- rem(tmpWord);
- // cerr << "word deleted\n";
- }
- int correct(int mStart, int mEnd) {
- int cur = mStart, pre;
- string curWord = "", newWord;
- // cerr << "correcting word\n";
- int ans = 0;
- while(1) {
- curWord = "";
- pre = cur;
- while(cur < words.length() && words[cur] != '_') {
- curWord += words[cur];
- cur++;
- }
- // cerr << "checking word = " << curWord << endl;
- newWord = "";
- if(!find(curWord) && search(curWord, newWord)) {
- // cerr << "found word = " << newWord << endl;
- for(int i = pre; i < cur; i++) {
- words[i] = newWord[i - pre];
- }
- ans += (newWord != curWord);
- }
- cur++;
- if(cur > mEnd) {
- break;
- }
- }
- // cerr << "ending correction\n" << endl;
- return ans;
- }
- void destory(char mResult[]) {
- for(int i = 0; i < words.length(); i++) {
- mResult[i] = words[i];
- }
- // cerr << "final result = " << words << endl;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement