Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <fstream>
- #include <string>
- #include <vector>
- #include <string.h>
- #include <cstdio>
- #include <assert.h>
- using namespace std;
- const int k=100;
- static const int buf_size = 4096;
- static int write_pos = 0;
- static char write_buf[buf_size];
- inline int readChar() {
- int c = getchar();
- while (c < 32)
- c = getchar();
- return c;
- }
- inline void writeChar( int x ) {
- if (write_pos == buf_size)
- fwrite(write_buf, 1, buf_size, stdout), write_pos = 0;
- write_buf[write_pos++] = x;
- }
- inline void writeWord( const char *s ) {
- while (*s)
- writeChar(*s++);
- }
- inline bool readWord( char *s ) {
- int c = readChar();
- while (c >= 32)
- *s++ = c, c = getchar();
- *s = 0;
- }
- inline int readInt() {
- int s = 0, c = readChar(), x = 0;
- if (c == '-')
- s = 1, c = getchar();
- while ('0' <= c && c <= '9')
- x = x * 10 + c - '0', c = getchar();
- return s ? -x : x;
- }
- struct bohr_vrtx{
- int next_vrtx[k],pat_num;
- bool flag;
- int suff_link; //suff_link - суффиксная ссылка
- int suff_flink; //suff_flink - "хорошая" суф. ссылка
- int auto_move[k],par; //auto_move - запоминание перехода автомата, par - вершина-отец в дереве
- char symb; //символ на ребре от par к этой вершине
- };
- bohr_vrtx bohr[80001];
- int sizeBohr = 0;
- int added = 0;
- bohr_vrtx make_bohr_vrtx(int p,char c){
- bohr_vrtx v;
- //(255)=(2^8-1)=(все единицы в каждом байте памяти)=(-1 в дополнительном коде целого 4-байтного числа int)
- memset(v.next_vrtx, 255, sizeof(v.next_vrtx));
- v.flag=false;
- v.suff_link=-1; //изначально - суф. ссылки нет
- memset(v.auto_move, 255, sizeof(v.auto_move));
- v.par=p;
- v.symb=c;
- v.suff_flink=-1;
- return v;
- }
- void bohr_ini(){
- //добавляем единственную вершину - корень
- bohr[sizeBohr++] = make_bohr_vrtx(0,0);
- }
- void add_string_to_bohr(const char * s, const int & len){
- int num=0; //начинаем с корня
- for (int i=0; i<len; i++){
- char ch=s[i]-32; //получаем номер в алфавите
- if (bohr[num].next_vrtx[ch]==-1){ //-1 - признак отсутствия ребра
- bohr[sizeBohr++] = make_bohr_vrtx(num, ch);
- bohr[num].next_vrtx[ch]=sizeBohr - 1;
- }
- num=bohr[num].next_vrtx[ch];
- }
- bohr[num].flag=true;
- added++;
- bohr[num].pat_num=added-1;
- }
- bool is_string_in_bohr(const char * s, const int & len){
- int num = 0;
- for (int i = 0; i < len; i++){
- char ch = s[i]-32;
- if (bohr[num].next_vrtx[ch] == -1){
- return false;
- }
- num=bohr[num].next_vrtx[ch];
- }
- return true;
- }
- int get_auto_move(int v, char ch);
- int get_suff_link(int v){
- if (bohr[v].suff_link == -1) //если еще не считали
- if (v == 0 || bohr[v].par == 0) //если v - корень или предок v - корень
- bohr[v].suff_link = 0;
- else
- bohr[v].suff_link = get_auto_move(get_suff_link(bohr[v].par), bohr[v].symb);
- return bohr[v].suff_link;
- }
- int get_auto_move(int v, char ch){
- if (bohr[v].auto_move[ch]==-1)
- if (bohr[v].next_vrtx[ch]!=-1)
- bohr[v].auto_move[ch]=bohr[v].next_vrtx[ch];
- else
- if (v==0)
- bohr[v].auto_move[ch]=0;
- else
- bohr[v].auto_move[ch]=get_auto_move(get_suff_link(v), ch);
- return bohr[v].auto_move[ch];
- }
- int get_suff_flink(int v){
- if (bohr[v].suff_flink==-1){
- int u=get_suff_link(v);
- if (u==0) //либо v - корень, либо суф. ссылка v указывает на корень
- bohr[v].suff_flink=0;
- else
- bohr[v].suff_flink=(bohr[u].flag)?u:get_suff_flink(u);
- }
- return bohr[v].suff_flink;
- }
- bool check(int v,int i){
- for(int u=v;u!=0;u=get_suff_flink(u)){
- if (bohr[u].flag) return true;
- }
- return false;
- }
- bool find_all_pos(const char * s, const int& len){
- int u=0;
- for(int i = 0; i < len; i++){
- u=get_auto_move(u,s[i]-32);
- if (check(u,i+1)) return true;
- }
- return false;
- }
- char s1[1000];
- int myAtoi(char * s, const int& len) {
- int n = 0;
- for (int i = 0; i < len; i++)
- n = n * 10 + (int)(s[i] - '0');
- return n;
- }
- inline void flush() {
- if (write_pos)
- fwrite(write_buf, 1, write_pos, stdout), write_pos = 0;
- }
- int main() {
- bohr_ini();
- int n;
- n = readInt();
- for (int i = 0; i < n; i++) {
- readWord(s1);
- add_string_to_bohr(s1, strlen(s1));
- };
- while (!feof(stdin)) {
- readWord(s1);
- if (find_all_pos(s1, strlen(s1))) {
- puts(s1);
- }
- }
- //system("pause");
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement