Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<bits/stdc++.h>
- using namespace std;
- const int N = 30005;
- const int K = 256;
- int node,flag,J;
- short fail[N], num[N];
- bool endMark[N], vis[N];
- string a[10003];
- vector<string>str;
- map<int,map<int,int>>Next;
- vector<pair<short,short>>vec;
- void init()
- {
- node = 0;
- for(int i = 0; i < N; i++) {
- endMark[i] = false;
- vis[i] = false;
- fail[i] = 0;
- num[i] = 0;
- }
- }
- void Insert(string s)
- {
- int v = 0;
- for(int i = 0; i < s.size(); i++) {
- int id = s[i] ;
- if(id<0)id=127-id;
- if(!vis[Next[id][v]]) {
- Next[id][v] = ++node;
- vis[node] = true;
- }
- v = Next[id][v];
- num[v]=i;
- }
- endMark[v] = true;
- }
- void build_fail()
- {
- queue<int>q;
- for(int i = 0; i < K; i++) {
- if(vis[Next[i][0]]) {
- q.push(Next[i][0]); // root's child
- }
- }
- while(!q.empty()) {
- int u = q.front();
- q.pop();
- for(int i = 0; i < K; i++) {
- int v = Next[i][u];
- if(vis[v]==0) continue;
- q.push(v);
- int p = fail[u];
- while(p && vis[Next[i][p]]==0) {
- p = fail[p];
- }
- fail[v] = Next[i][p];
- }
- }
- }
- void Search(string s)
- {
- int v = 0;
- for(int i = 0; i < s.size(); i++) {
- int id = s[i] ;
- if(id<0)id=127-id;
- while(v && !vis[Next[id][v]]) {
- v = fail[v];
- }
- v = Next[id][v];
- int tmp = v;
- while(tmp) {
- if(endMark[tmp])
- {
- //cout<<tmp<<" "<<v<<endl;
- vec.push_back({J+1,i-num[tmp]+1});
- flag=1;
- //return;
- }
- tmp = fail[tmp];
- }
- }
- }
- int main()
- {
- int n,m,i,j,k;
- cin>>n;
- getchar();
- for(i=0;i<n;i++)
- {
- getline(cin,a[i]);
- }
- cin>>m;
- str.resize(m+1);
- getchar();
- for(i=0;i<m;i++) {
- getline(cin,str[i]);
- }
- for(i=0;i<n;i++)
- {
- Insert(a[i]);
- if(node>20000)
- {
- build_fail();
- for(J=0;J<m;J++)
- {
- Search(str[J]);
- //if(flag)break;
- }
- init();
- Next.clear();
- }
- }
- build_fail();
- for(J=0;J<m;J++)
- {
- Search(str[J]);
- //if(flag)break;
- }
- sort(vec.begin(),vec.end());
- if(flag==0)cout<<"Passed"<<endl;
- else
- cout<<vec[0].first<<" "<<vec[0].second<<endl;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement