Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <cstdio>
- #include <queue>
- #include <cstring>
- #include <bitset>
- #include <iostream>
- using namespace std;
- const int MAXR = 105;
- const int MAXN = 5005;
- const int MAXL = 30;
- const int MAXK = 4;
- struct Trie
- {
- //int iEnd;
- int iEnd;
- //vector <int> v;
- int mask[MAXK];
- Trie* child[MAXL];
- Trie* nv, *openLink;
- };
- void init(Trie* &temp)
- {
- //printf("DSA");
- temp = new Trie();
- temp->iEnd = -1;
- for(int i = 0; i < MAXL; i++)
- {
- temp->child[i] = nullptr;
- }
- temp->nv = nullptr; temp->openLink = nullptr;
- }
- Trie* root;
- int n, m, r, c;
- char str1[MAXR][MAXR];
- char str2[MAXN][MAXN];
- void add_word(Trie* &tree, int num, int f, int temp)
- {
- //printf("%d %d\n", str1[temp][f], num);
- if(temp == r)
- {
- //if(tree->iEnd == -1)
- //tree->v.push_back(num);
- int mask = num / 30;
- int pos = num % 30;
- tree->mask[mask] |= (1 << pos);
- //printf("DSA");
- tree->iEnd = num;
- //tree->iEnd = num;
- }
- else
- {
- //printf("DSA");
- //printf("%d\n", t[0]);
- if(tree->child[str1[temp][f]] == nullptr)
- {
- init(tree->child[str1[temp][f]]);
- }
- add_word(tree->child[str1[temp][f]], num, f, temp + 1);
- }
- }
- void read_input()
- {
- scanf("%d %d", &r, &c);
- for(int i = 0; i < r; i++)
- {
- scanf("%s", str1[i]);
- }
- for(int i = 0; i < r; i++)
- {
- for(int j = 0; j < c; j++)
- {
- str1[i][j] -= 'a';
- }
- }
- //printf("DSA");
- init(root);
- for(int i = 0; i < c; i++)
- {
- add_word(root, i, i, 0);
- }
- scanf("%d %d", &n, &m);
- for(int i = 0; i < n; i++)
- {
- scanf("%s", str2[i]);
- }
- for(int i = 0; i < n; i++)
- {
- for(int j = 0; j < m; j++)
- {
- str2[i][j] -= 'a';
- }
- }
- }
- void pre_links()
- {
- queue <Trie*> q;
- root->nv = root;
- for(int i = 0; i < MAXL; i++)
- {
- if(root->child[i] != nullptr)
- {
- root->child[i]->nv = root;
- q.push(root->child[i]);
- }
- }
- while(!q.empty())
- {
- Trie* v = q.front(); q.pop();
- for(int x = 0; x < MAXL; x++)
- {
- if(v->child[x] != nullptr)
- {
- Trie* w = v->child[x];
- q.push(w);
- Trie* vw = v->nv;
- while(vw->child[x] == nullptr && vw != root)
- {
- vw = vw->nv;
- }
- if(vw->child[x] != nullptr)
- {
- w->nv = vw->child[x];
- }
- else
- {
- w->nv = root;
- }
- if(w->nv->iEnd != -1)
- {
- w->openLink = w->nv;
- }
- else if(w->nv->openLink != nullptr)
- {
- w->openLink = w->nv->openLink;
- }
- }
- }
- }
- }
- int ans;
- int o;
- int current[2][MAXN][MAXK];
- void report_end(int masks[MAXK], int row)
- {
- int temp = (current[o ^ 1][row][0] << 1) & masks[0];
- current[o][row][0] |= temp;
- for(int i = 0; i < MAXK; i++)
- {
- temp = (current[o ^ 1][row][i] << 1) & masks[i];
- current[o][row][i] |= temp;
- if(current[o ^ 1][row][i - 1] & (1 << 29))
- {
- current[o][row][i] |= 1;
- }
- }
- //printf("%d %d\n", masks[0], row);
- //cout << bitset<2>(current[o ^ 1][row][0]) << "\n";
- int mask = (c - 1) / 30;
- int pos = (c - 1) % 30;
- //printf("%d\n", current[o][row][2]);
- if(current[o][row][mask] & (1 << pos))
- {
- ans++;
- }
- if(masks[0] & 1)
- {
- //printf("DSA\n");
- current[o][row][0] |= 1;
- }
- //printf("%d %d %d\n", nd, temp, row);
- /*int z = 5;
- for(int i = z - 1; i >= 0; i--)
- {
- //printf("%d\n", z);
- int nd = 5;
- if(nd == 0)
- {
- //printf("%d %d %d\n", nd, row, temp);
- current[row][nd] = temp;
- if(nd == c - 1)
- {
- ans++;
- }
- }
- int prev = current[row][nd - 1];
- //printf("%d %d %d %d\n", nd, row, temp, prev);
- if(temp - prev == 1 && prev != -1)
- {
- if(nd == c - 1)
- {
- ans++;
- }
- current[row][nd] = temp;
- }
- }*/
- }
- void full_ac(int coll)
- {
- int i = 0;
- Trie* w = root;
- Trie* w1;
- do
- {
- w1 = w->child[str2[i][coll]];
- while(w1 != nullptr)
- {
- if(w1->iEnd != -1)
- {
- report_end(w1->mask, i);
- }
- if(w1->openLink != nullptr)
- {
- if(w1->openLink->iEnd != -1)
- {
- report_end(w1->openLink->mask, i);
- }
- }
- w = w1;
- i++;
- if(i >= n)
- {
- break;
- }
- w1 = w->child[str2[i][coll]];
- }
- if(w != root)
- {
- w = w->nv;
- }
- else
- {
- i++;
- }
- }while(i < n);
- }
- bool temp[MAXR];
- void solve()
- {
- //memset(current, -1, sizeof(current));
- for(int i = 0; i < m; i++)
- {
- full_ac(i);
- for(int j = 0; j < n; j++)
- {
- for(int z = 0; z < MAXK; z++)
- {
- current[o ^ 1][j][z] = 0;
- }
- }
- o ^= 1;
- }
- printf("%d\n", ans);
- }
- int main()
- {
- read_input();
- pre_links();
- solve();
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement