Advertisement
Rkhamim

Untitled

Jan 23rd, 2021
351
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.59 KB | None | 0 0
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. const int N = 30005;
  4. const int K = 256;
  5. int node,flag,J;
  6. short fail[N], num[N];
  7. bool endMark[N], vis[N];
  8. string a[10003];
  9. vector<string>str;
  10. map<int,map<int,int>>Next;
  11. vector<pair<short,short>>vec;
  12. void init()
  13. {
  14. node = 0;
  15. for(int i = 0; i < N; i++) {
  16. endMark[i] = false;
  17. vis[i] = false;
  18. fail[i] = 0;
  19. num[i] = 0;
  20. }
  21. }
  22. void Insert(string s)
  23. {
  24. int v = 0;
  25. for(int i = 0; i < s.size(); i++) {
  26. int id = s[i] ;
  27. if(id<0)id=127-id;
  28. if(!vis[Next[id][v]]) {
  29. Next[id][v] = ++node;
  30. vis[node] = true;
  31. }
  32. v = Next[id][v];
  33. num[v]=i;
  34. }
  35. endMark[v] = true;
  36. }
  37.  
  38. void build_fail()
  39. {
  40. queue<int>q;
  41. for(int i = 0; i < K; i++) {
  42. if(vis[Next[i][0]]) {
  43. q.push(Next[i][0]); // root's child
  44. }
  45. }
  46. while(!q.empty()) {
  47. int u = q.front();
  48. q.pop();
  49. for(int i = 0; i < K; i++) {
  50. int v = Next[i][u];
  51. if(vis[v]==0) continue;
  52. q.push(v);
  53. int p = fail[u];
  54. while(p && vis[Next[i][p]]==0) {
  55. p = fail[p];
  56. }
  57. fail[v] = Next[i][p];
  58. }
  59. }
  60. }
  61. void Search(string s)
  62. {
  63. int v = 0;
  64. for(int i = 0; i < s.size(); i++) {
  65. int id = s[i] ;
  66. if(id<0)id=127-id;
  67. while(v && !vis[Next[id][v]]) {
  68. v = fail[v];
  69. }
  70. v = Next[id][v];
  71. int tmp = v;
  72. while(tmp) {
  73. if(endMark[tmp])
  74. {
  75. //cout<<tmp<<" "<<v<<endl;
  76. vec.push_back({J+1,i-num[tmp]+1});
  77. flag=1;
  78. //return;
  79. }
  80. tmp = fail[tmp];
  81. }
  82. }
  83. }
  84. int main()
  85. {
  86. int n,m,i,j,k;
  87. cin>>n;
  88. getchar();
  89. for(i=0;i<n;i++)
  90. {
  91. getline(cin,a[i]);
  92. }
  93. cin>>m;
  94. str.resize(m+1);
  95. getchar();
  96. for(i=0;i<m;i++) {
  97. getline(cin,str[i]);
  98. }
  99. for(i=0;i<n;i++)
  100. {
  101. Insert(a[i]);
  102. if(node>20000)
  103. {
  104. build_fail();
  105. for(J=0;J<m;J++)
  106. {
  107. Search(str[J]);
  108. //if(flag)break;
  109. }
  110. init();
  111. Next.clear();
  112. }
  113. }
  114. build_fail();
  115. for(J=0;J<m;J++)
  116. {
  117. Search(str[J]);
  118. //if(flag)break;
  119. }
  120. sort(vec.begin(),vec.end());
  121. if(flag==0)cout<<"Passed"<<endl;
  122. else
  123. cout<<vec[0].first<<" "<<vec[0].second<<endl;
  124. return 0;
  125. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement