Advertisement
Guest User

Untitled

a guest
Mar 29th, 2015
213
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 4.94 KB | None | 0 0
  1. #include <iostream>
  2. #include <fstream>
  3. #include <string>
  4. #include <vector>
  5. #include <string.h>
  6. #include <cstdio>
  7. #include <assert.h>
  8.  
  9. using namespace std;
  10.  
  11.  
  12. const int k=100;
  13.  
  14. static const int buf_size = 4096;
  15. static int write_pos = 0;
  16. static char write_buf[buf_size];
  17.  
  18.  
  19. inline int readChar() {
  20. int c = getchar();
  21. while (c < 32)
  22. c = getchar();
  23. return c;
  24. }
  25.  
  26.  
  27. inline void writeChar( int x ) {
  28. if (write_pos == buf_size)
  29. fwrite(write_buf, 1, buf_size, stdout), write_pos = 0;
  30. write_buf[write_pos++] = x;
  31. }
  32.  
  33. inline void writeWord( const char *s ) {
  34. while (*s)
  35. writeChar(*s++);
  36. }
  37.  
  38.  
  39. inline bool readWord( char *s ) {
  40. int c = readChar();
  41. while (c >= 32)
  42. *s++ = c, c = getchar();
  43. *s = 0;
  44. }
  45.  
  46.  
  47.  
  48. inline int readInt() {
  49. int s = 0, c = readChar(), x = 0;
  50. if (c == '-')
  51. s = 1, c = getchar();
  52. while ('0' <= c && c <= '9')
  53. x = x * 10 + c - '0', c = getchar();
  54. return s ? -x : x;
  55. }
  56.  
  57.  
  58. struct bohr_vrtx{
  59. int next_vrtx[k],pat_num;
  60. bool flag;
  61. int suff_link; //suff_link - суффиксная ссылка
  62. int suff_flink; //suff_flink - "хорошая" суф. ссылка
  63. int auto_move[k],par; //auto_move - запоминание перехода автомата, par - вершина-отец в дереве
  64. char symb; //символ на ребре от par к этой вершине
  65. };
  66.  
  67. bohr_vrtx bohr[80001];
  68. int sizeBohr = 0;
  69. int added = 0;
  70.  
  71. bohr_vrtx make_bohr_vrtx(int p,char c){
  72. bohr_vrtx v;
  73. //(255)=(2^8-1)=(все единицы в каждом байте памяти)=(-1 в дополнительном коде целого 4-байтного числа int)
  74. memset(v.next_vrtx, 255, sizeof(v.next_vrtx));
  75. v.flag=false;
  76. v.suff_link=-1; //изначально - суф. ссылки нет
  77. memset(v.auto_move, 255, sizeof(v.auto_move));
  78. v.par=p;
  79. v.symb=c;
  80. v.suff_flink=-1;
  81. return v;
  82. }
  83.  
  84.  
  85.  
  86. void bohr_ini(){
  87. //добавляем единственную вершину - корень
  88. bohr[sizeBohr++] = make_bohr_vrtx(0,0);
  89. }
  90.  
  91.  
  92.  
  93. void add_string_to_bohr(const char * s, const int & len){
  94. int num=0; //начинаем с корня
  95. for (int i=0; i<len; i++){
  96. char ch=s[i]-32; //получаем номер в алфавите
  97. if (bohr[num].next_vrtx[ch]==-1){ //-1 - признак отсутствия ребра
  98. bohr[sizeBohr++] = make_bohr_vrtx(num, ch);
  99. bohr[num].next_vrtx[ch]=sizeBohr - 1;
  100. }
  101. num=bohr[num].next_vrtx[ch];
  102. }
  103. bohr[num].flag=true;
  104. added++;
  105. bohr[num].pat_num=added-1;
  106. }
  107.  
  108.  
  109. bool is_string_in_bohr(const char * s, const int & len){
  110. int num = 0;
  111. for (int i = 0; i < len; i++){
  112. char ch = s[i]-32;
  113. if (bohr[num].next_vrtx[ch] == -1){
  114. return false;
  115. }
  116. num=bohr[num].next_vrtx[ch];
  117. }
  118. return true;
  119. }
  120.  
  121. int get_auto_move(int v, char ch);
  122.  
  123. int get_suff_link(int v){
  124. if (bohr[v].suff_link == -1) //если еще не считали
  125. if (v == 0 || bohr[v].par == 0) //если v - корень или предок v - корень
  126. bohr[v].suff_link = 0;
  127. else
  128. bohr[v].suff_link = get_auto_move(get_suff_link(bohr[v].par), bohr[v].symb);
  129. return bohr[v].suff_link;
  130. }
  131.  
  132.  
  133.  
  134. int get_auto_move(int v, char ch){
  135. if (bohr[v].auto_move[ch]==-1)
  136. if (bohr[v].next_vrtx[ch]!=-1)
  137. bohr[v].auto_move[ch]=bohr[v].next_vrtx[ch];
  138. else
  139. if (v==0)
  140. bohr[v].auto_move[ch]=0;
  141. else
  142. bohr[v].auto_move[ch]=get_auto_move(get_suff_link(v), ch);
  143. return bohr[v].auto_move[ch];
  144. }
  145.  
  146.  
  147. int get_suff_flink(int v){
  148. if (bohr[v].suff_flink==-1){
  149. int u=get_suff_link(v);
  150. if (u==0) //либо v - корень, либо суф. ссылка v указывает на корень
  151. bohr[v].suff_flink=0;
  152. else
  153. bohr[v].suff_flink=(bohr[u].flag)?u:get_suff_flink(u);
  154. }
  155. return bohr[v].suff_flink;
  156. }
  157.  
  158. bool check(int v,int i){
  159. for(int u=v;u!=0;u=get_suff_flink(u)){
  160. if (bohr[u].flag) return true;
  161. }
  162. return false;
  163. }
  164.  
  165.  
  166. bool find_all_pos(const char * s, const int& len){
  167. int u=0;
  168. for(int i = 0; i < len; i++){
  169. u=get_auto_move(u,s[i]-32);
  170. if (check(u,i+1)) return true;
  171. }
  172. return false;
  173. }
  174.  
  175. char s1[1000];
  176.  
  177.  
  178. int myAtoi(char * s, const int& len) {
  179. int n = 0;
  180. for (int i = 0; i < len; i++)
  181. n = n * 10 + (int)(s[i] - '0');
  182. return n;
  183. }
  184.  
  185. inline void flush() {
  186. if (write_pos)
  187. fwrite(write_buf, 1, write_pos, stdout), write_pos = 0;
  188. }
  189.  
  190. int main() {
  191. bohr_ini();
  192. int n;
  193. n = readInt();
  194. for (int i = 0; i < n; i++) {
  195. readWord(s1);
  196. add_string_to_bohr(s1, strlen(s1));
  197. };
  198. while (!feof(stdin)) {
  199. readWord(s1);
  200. if (find_all_pos(s1, strlen(s1))) {
  201. puts(s1);
  202. }
  203. }
  204. //system("pause");
  205. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement