# bzoj 1590 [Usaco2008 Dec]Secret Message 秘密信息

### Output

#### Sample Input

4 5

3 0 1 0

1 1

3 1 0 0

3 1 1 0

1 0

1 1

2 0 1

5 0 1 0 0 1

2 1 1

INPUT DETAILS:

Four messages; five codewords.

1

3

1

1

2

### HINT

0 matches only 010: 1 match 1 matches 1, 100, and 110: 3 matches 01 matches only 010: 1 match 01001 matches 010: 1 match 11 matches 1 and 110: 2 matches

### 题解

#include <cstdio>
#include <cstring>
#define N 500010
#define getchar() (S == T && (T = (S = BB) + fread(BB, 1, 1 << 15, stdin), S == T) ? EOF : *S++)
using namespace std;
char BB[1 << 15], *S = BB, *T = BB;
{
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
int ch[N][2],sums[N],cnt[N],a[N],root=1,sz=1;
{
int now=root;
for (int i=1;i<=n;i++)
{
if (ch[now][a[i]])
now=ch[now][a[i]];
else
now=ch[now][a[i]]=++sz;
cnt[now]++;
}
sums[now]++;
}
{
int now=root,ans=0;
for (int i=1;i<=n;now=ch[now][a[i]],i++)
if (!ch[now][a[i]])
return ans;
else if (i!=n)
ans+=sums[ch[now][a[i]]];
else
ans+=cnt[ch[now][a[i]]];
return ans;
}
main()
{
for (int i=1;i<=n;i++)
{
for (int j=1;j<=k;j++)