[noi1755]Trie

定义S对应的数组为$a_{i}=\min_{0\le j<i,S_{j}=S_{i}}i-j$，特别的，若不存在j，令$a_{i}=i$，那么容易发现存在双射关系就意味这两者对应的数组相同

因此，考虑需要单词为$a_{i}$，询问串对应的为$b_{i}$，那么如果$b[i,i+l_{a})$与$a$存在双射，当且仅当对于任意j，都有$a_{j}=b_{i+j}\vee (a_{j}=j\wedge b_{i+j}>j)$

具体的，使用AC自动机来判断，由于$b_{i+j}>j$的判断，因此要存储当前节点的深度

 1 #include<bits/stdc++.h>

 2 using namespace std;

 3 #define N 100005

 4 int V,n,m,l,las[31],d[N],vis[N],nex[N],a[N*5];

 5 char s[N*5];

 6 queue<int>q;

 7 map<int,int>ch[N];

 8 map<int,int>::iterator it;

 9 void hash(){

10     memset(las,-1,sizeof(las));

11     for(int i=0;i<l;i++){

12         a[i]=i-las[s[i]-'A'];

13         las[s[i]-'A']=i;

14     }

15 }

16 void add(){

17     int k=0;

18     for(int i=0;i<l;i++){

19         if (!ch[k][a[i]])ch[k][a[i]]=++V;

20         k=ch[k][a[i]];

21         d[k]=i+1;

22     }

23     vis[k]=1;

24 }

25 bool query(){

26     int k=0;

27     for(int i=0;i<l;i++){

28         while ((k)&&(!ch[k][min(a[i],d[k]+1)]))k=nex[k];

29         if (ch[k][min(a[i],d[k]+1)])k=ch[k][min(a[i],d[k]+1)];

30         if (vis[k])return 1;

31     }

32     return 0;

33 }

34 void bfs(){

35     q.push(0);

36     while (!q.empty()){

37         int k=q.front();

38         q.pop();

39         vis[k]|=vis[nex[k]];

40         for(it=ch[k].begin();it!=ch[k].end();it++){

41             int i=nex[k];

42             while ((i)&&(!ch[i][min((*it).first,d[i]+1)]))i=nex[i];

43             q.push((*it).second);

44             if (k)nex[(*it).second]=ch[i][min((*it).first,d[i]+1)];

45         }

46     }

47 }

48 int main(){

49     scanf("%d",&n);

50     for(int i=1;i<=n;i++){

51         scanf("%s",s);

52         l=strlen(s);

53         hash();

54         add();

55     }

56     bfs();

57     scanf("%d",&m);

58     for(int i=1;i<=m;i++){

59         scanf("%s",s);

60         l=strlen(s);

61         hash();

62         if (query())printf("Yes\n");

63         else printf("No\n");

64     }

65 }

巴特西

[noi1755]Trie

最新文章

热门文章