[关闭]
@Jerusalem 2015-11-11T11:35:09.000000Z 字数 1956 阅读 1077

BZOJ2938



  我们观察到可以构造出字符串满足题意的充分必要条件是,以病毒代码构造的Trie图有环。
  
  让我们考虑命题的证明,充分性是显然的,下证必要性。

  假设构造出了满足题意的字符串S,那么对于S[i],其在AC自动机上对应节点及其后缀链接必然是非单词的。很容易发现,遍历了所有对应节点后,下一个节点一定会形成环。
  
  Q.E.D


  1. #include <cstdio>
  2. #include <cstdlib>
  3. #include <cmath>
  4. #include <cstring>
  5. #include <algorithm>
  6. #include <iostream>
  7. #include <queue>
  8. using namespace std;
  9. const int maxnode=30005,sigma=2;
  10. struct Trie{
  11. int tot;
  12. int ch[maxnode][sigma];
  13. int val[maxnode];
  14. int f[maxnode];
  15. bool danger[maxnode];
  16. int last[maxnode];
  17. bool ins[maxnode];
  18. bool used[maxnode];
  19. Trie(){
  20. tot=1;
  21. memset(ch,0,sizeof(ch));
  22. memset(danger,false,sizeof(danger));
  23. memset(f,0,sizeof(f));
  24. memset(last,0,sizeof(last));
  25. memset(ins,false,sizeof(ins));
  26. memset(used,false,sizeof(used));
  27. }
  28. inline int idx(char a){
  29. return a-'0';
  30. }
  31. void Clear(){
  32. tot=1;
  33. memset(danger,false,sizeof(danger));
  34. memset(ch[0],0,sizeof(ch[0]));
  35. memset(used,false,sizeof(used));
  36. memset(ins,false,sizeof(ins));
  37. }
  38. int newnode(){
  39. memset(ch[tot],0,sizeof(ch[tot]));
  40. return tot++;
  41. }
  42. void Insert(string s){
  43. int len=s.length();
  44. int u=0;
  45. for(int i=0;i<len;i++){
  46. if(ch[u][idx(s[i])]==0)
  47. ch[u][idx(s[i])]=newnode();
  48. u=ch[u][idx(s[i])];
  49. }
  50. danger[u]=true;
  51. }
  52. void Build(){
  53. queue<int> Q;
  54. while(!Q.empty())
  55. Q.pop();
  56. for(int i=0;i<sigma;i++)
  57. if(ch[0][i]){
  58. Q.push(ch[0][i]);
  59. last[ch[0][i]]=f[ch[0][i]]=0;
  60. }
  61. while(!Q.empty()){
  62. int u=Q.front();
  63. Q.pop();
  64. for(int i=0;i<sigma;i++){
  65. if(ch[u][i]==0){
  66. ch[u][i]=ch[f[u]][i];
  67. continue;
  68. }
  69. int v=ch[u][i];
  70. Q.push(v);
  71. int r=f[u];
  72. while(r&&ch[r][i]==0)
  73. r=f[r];
  74. f[v]=ch[r][i];
  75. danger[v]|=danger[f[v]];
  76. }
  77. }
  78. }
  79. bool HaveRing(int from){
  80. ins[from]=true;
  81. for(int i=0;i<sigma;i++){
  82. if(ins[ch[from][i]])
  83. return true;
  84. if(danger[ch[from][i]]||used[ch[from][i]])
  85. continue;
  86. used[from]=true;
  87. if(HaveRing(ch[from][i]))
  88. return true;
  89. }
  90. ins[from]=false;
  91. return false;
  92. }
  93. };
  94. Trie Aho_Corasick;
  95. string S;
  96. int n;
  97. void Solve()
  98. {
  99. Aho_Corasick.Build();
  100. if(Aho_Corasick.HaveRing(0))
  101. cout<<"TAK";
  102. else
  103. cout<<"NIE";
  104. }
  105. void ReadData()
  106. {
  107. freopen("BZOJ2938.in","r",stdin);
  108. scanf("%d",&n);
  109. for(int i=1;i<=n;i++){
  110. cin>>S;
  111. Aho_Corasick.Insert(S);
  112. }
  113. }
  114. void Close()
  115. {
  116. fclose(stdin);
  117. fclose(stdout);
  118. }
  119. int main()
  120. {
  121. ReadData();
  122. Solve();
  123. Close();
  124. return 0;
  125. }
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注