后缀自动机

2019-11-14 17:22栏目:网络技术
TAG:

bzoj2938【Poi2000】病毒

 

[Poi2000]公共串

Time Limit: 3 Sec  Memory Limit: 128 MB
Submit: 1386  Solved: 620
[Submit][Status][Discuss]

2938: [Poi2000]病毒

Time Limit: 1 Sec Memory Limit: 128 MB
Submit: 345 Solved: 176
[Submit][Status][Discuss]

Description

 

       给出几个由小写字母构成的单词,求它们最长的公共子串的长度。

任务:

l        读入单词

l        计算最长公共子串的长度

l        输出结果

 

Description

二进制病毒审查委员会最近发现了如下的规律:某些确定的二进制串是病毒的代码。如果某段代码中不存在任何一段病毒代码,那么我们就称这段代码是安全的。现在委员会已经找出了所有的病毒代码段,试问,是否存在一个无限长的安全的二进制代码。

示例:

例如如果{011, 11, 00000}为病毒代码段,那么一个可能的无限长安全代码就是010101…。如果{01, 11, 000000}为病毒代码段,那么就不存在一个无限长的安全代码。

任务:

请写一个程序:

l 读入病毒代码;

l 判断是否存在一个无限长的安全代码;

l 将结果输出

Input

 

文件的第一行是整数 n,1<=n<=5,表示单词的数量。接下来n行每行一个单词,只由小写字母组成,单词的长度至少为1,最大为2000。

 

Input

 

第一行包括一个整数n,表示病毒代码段的数目。以下的n行每一行都包括一个非空的01字符串——就是一个病毒代码段。所有病毒代码段的总长度不超过30000。

Output

仅一行,一个整数,最长公共子串的长度。

 

Output

你应在在文本文件WIN.OUT的第一行输出一个单词:

l TAK——假如存在这样的代码;

l NIE——如果不存在。

Sample Input

3
abcb
bca
acbc

Sample Input

3
01
11
00000

Sample Output

Sample Output

NIE

HINT

后缀自动机

 1 #include<cmath>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<iostream>
 5 #include<algorithm>
 6 
 7 #define N 2007
 8 using namespace std;
 9 inline int read()
10 {
11     int x=0,f=1;char ch=getchar();
12     while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
13     while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
14     return x*f;
15 }
16 
17 int n;
18 char ch[N];
19 
20 struct SAM
21 {
22     int cnt,last;
23     int fa[4005],a[4005][27],mx[4005],len[4005],ans[4005];
24     int v[4005],q[4005];
25     SAM(){last=++cnt;}
26     void extend(int c)
27     {
28         int p=last,np=last=++cnt;mx[np]=mx[p]+1;
29         while(!a[p][c]&&p)a[p][c]=np,p=fa[p];
30         if(!p)fa[np]=1;
31         else 
32         {
33             int q=a[p][c];
34             if(mx[p]+1==mx[q])fa[np]=q;
35             else 
36             {
37                 int nq=++cnt;mx[nq]=mx[p]+1;
38                 memcpy(a[nq],a[q],sizeof(a[q]));
39                 fa[nq]=fa[q];
40                 fa[np]=fa[q]=nq;
41                 while(a[p][c]==q)a[p][c]=nq,p=fa[p];
42             }
43         }
44     }
45     void pre()
46     {
47         for(int i=1;i<=cnt;i++)ans[i]=mx[i];
48         for(int i=1;i<=cnt;i++)v[mx[i]]++;
49         for(int i=1;i<=cnt;i++)v[i]+=v[i-1];
50         for(int i=cnt;i;i--)q[v[mx[i]]--]=i;
51     }
52     void solve()
53     {
54         scanf("%s",ch+1);
55         memset(len,0,sizeof(len));
56         int l=strlen(ch+1),p=1,tmp=0;
57         for(int i=1;i<=l;i++)
58         {
59             int c=ch[i]-'a';
60             while(!a[p][c]&&p)p=fa[p];
61             if(p==0)p=1,tmp=0;
62             else tmp=min(tmp,mx[p])+1,p=a[p][c];
63             len[p]=max(len[p],tmp);
64         }
65         for(int i=cnt;i;i--)len[fa[q[i]]]=max(len[fa[q[i]]],len[q[i]]);
66         for(int i=1;i<=cnt;i++)ans[i]=min(ans[i],len[i]);
67     }
68 }sam;
69 int main()
70 {
71     n=read();scanf("%s",ch+1);
72     int l=strlen(ch+1);
73     for(int i=1;i<=l;i++)sam.extend(ch[i]-'a');
74     sam.pre();
75     for(int i=1;i<n;i++)sam.solve();
76     int ans=0;
77     for(int i=1;i<=sam.cnt;i++)
78         ans=max(ans,sam.ans[i]);
79     printf("%dn",ans);
80 }

 

HINT

 

Source

这道题的思路很好

首先我们跑一次AC自动机,Trie树和失配边就构成了一个有向图。那么,能找到一个无限长的安全代码,当且仅当在非单词节点中存在环,用拓扑排序判断即可。

#include
#include
#include
#include
#include
#include
#include
#define F(i,j,n) for(int i=j;i<=n;i++)
#define D(i,j,n) for(int i=j;i>=n;i--)
#define ll long long
#define pa pair
#define maxn 30100
#define inf 1000000000
using namespace std;
struct edge_type
{
 int next,to;
}e[maxn*2];
int go[maxn],in[maxn],head[maxn],t[maxn][2];
int n,tot=1,cnt=0;
bool v[maxn];
char s[maxn];
inline void add_edge(int x,int y)
{
 e[++cnt]=(edge_type){head[x],y};
 head[x]=cnt;
}
inline void insert()
{
 scanf("%s",s);
 int len=strlen(s),now=1;
 F(i,0,len-1)
 {
  int x=s[i]-'0';
  if (!t[now][x]) t[now][x]=++tot;
  now=t[now][x];
 }
 v[now]=true;
}
inline void bfs()
{
 queue q;
 q.push(1);
 while (!q.empty())
 {
  int x=q.front(),y,j;q.pop();v[x]|=v[go[x]];
  F(i,0,1)
  {
   j=go[x];
   while (j&&!t[j][i]) j=go[j];
   if (t[x][i])
   {
    go[y=t[x][i]]=j?t[j][i]:1;
    q.push(y);
   }
   else t[x][i]=j?t[j][i]:1;
  }
 }
}
inline bool topsort()
{
 queue q;
 int sum=0;
 F(i,1,tot)
 {
  if (v[i]) sum++;
  else F(j,0,1) if (!v[t[i][j]])
  {
   add_edge(i,t[i][j]);
   in[t[i][j]]++;
  }
 }
 F(i,1,tot) if (!v[i]&&!in[i]) q.push(i);
 while (!q.empty())
 {
  int x=q.front();q.pop();sum++;
  for(int i=head[x];i;i=e[i].next)
  {
   int y=e[i].to;
   in[y]--;
   if (!in[y]) q.push(y);
  }
 }
 return sum==tot;
}
int main()
{
 scanf("%d",&n);
 F(i,1,n) insert();
 bfs();
 printf("%sn",topsort()?"NIE":"TAK");
 return 0;
}

2938: [Poi2000]病毒 Time Limit: 1 Sec Memory Limit: 128 MB Submit: 345 Solved: 176 [Submit][Status][Discuss] Description 二进制病毒审查委员会最...

版权声明:本文由澳门新葡亰平台游戏发布于网络技术,转载请注明出处:后缀自动机