Description：

给出 $n$ 个数字串，求用以下四种方式划分区间这些串，都不在一个区间中连续出现的串的个数。

$xxx|xxx|xxxxx$ $xxx|xxxx|xxxx$ $xxxx|xxxx|xxx$ $xxxx|xxx|xxxx$

Solution：

建出 $AC$ 自动机，对每个点记录一下这个点可能代表的串长度为几，在求 $fail$ 时或上 $fail$ 的值，因为找到这个位置其实也就找到了 $fail$ 链上的所有状态，所以 $fail$ 链上如果有串和他长度不同的话，应该记录下来，转移时分类讨论长度是否正好在某个整区间内即可。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<map>

#include<cstring>

using namespace std;

int n;

#define MAXN 101

struct node

{

	int tr[10];

	int fail;

	int dep;

	node(){memset(tr,0,sizeof(tr));dep = 0;}

}t[MAXN * 5];

int ptr = 0;

inline int newnode(){return ++ptr;}

int root;

inline void insert(char c[])

{

	register int l = strlen(c + 1);

	register int cur = root;

	for(register int i = 1;i <= l;++i)

	{

		if(t[cur].tr[c[i] - '0'] == 0)

			t[cur].tr[c[i] - '0'] = newnode();

		cur = t[cur].tr[c[i] - '0'];

	}

	t[cur].dep |= (1 << l);

	return;

}

int q[MAXN * 5];

inline void make_fail()

{

	int head = 1,tail = 0;

	for(register int i = 0;i <= 9;++i)

	{

		if(t[root].tr[i] != 0)

		{

			t[t[root].tr[i]].fail = root;

			q[++tail] = t[root].tr[i];

		}

	}

	while(head <= tail)

	{

		register int k = q[head++];

		for(int i = 0;i <= 9;++i)

		{

			if(t[k].tr[i] != 0)

			{

				int p = t[k].fail;

				while(p && t[p].tr[i] == 0)p = t[p].fail;

				t[t[k].tr[i]].fail = t[p].tr[i];

				t[t[k].tr[i]].dep |= t[t[p].tr[i]].dep;

				q[++tail] = t[k].tr[i];

			}

			else

			{

				t[k].tr[i] = t[t[k].fail].tr[i];

			}

		}

	}

	return;

}

typedef long long ll;

ll f[12][501];

ll dfs(int len,int pos)

{

	if(t[pos].dep)

	{

		for(int i = 1;i <= 5;++i)

		{

			if(t[pos].dep & (1 << i))

			{

				if(len >= 7 && len + i <= 11)return 0;

				if(len >= 4 && len + i <= 8)return 0;

				if(len >= 3 && len + i <= 7)return 0;

				if(len >= 0 && len + i <= 5)return 0;

			}

		}

	}

	if(len == 0)return 1;

	if(f[len][pos] != -1)return f[len][pos];

	register ll res = 0;

	for(int i = 0;i <= 9;++i)

	{

		res += dfs(len - 1,t[pos].tr[i]);

	}

	f[len][pos] = res;

	return res;

}

int main()

{

	memset(f,-1,sizeof(f));

	scanf("%d",&n);

	char str[8];

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

	{

		scanf("%s",str + 1);

		insert(str);

	}

	make_fail();

	register int cur = 0;cur = t[root].tr[1];

	printf("%lld\n",dfs(10,cur));

	return 0;

}

其实这题可以分别记录四个节点的位置，如果到了区间边界就跳根，用 $map$ 记录状态也能过。

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<map>

#include<cstring>

using namespace std;

int n;

#define MAXN 101

struct node

{

	int tr[10];

	bool tag;

	int fail;

	node(){memset(tr,0,sizeof(tr));tag = false;}

}t[MAXN * 5];

int ptr = 0;

inline int newnode(){return ++ptr;}

int root;

inline void insert(char c[])

{

	register int l = strlen(c + 1);

	register int cur = root;

	for(register int i = 1;i <= l;++i)

	{

		if(t[cur].tag)return;

		if(t[cur].tr[c[i] - '0'] == 0)

			t[cur].tr[c[i] - '0'] = newnode();

		cur = t[cur].tr[c[i] - '0'];

	}

	t[cur].tag = true;

	return;

}

int q[MAXN * 5];

inline void make_fail()

{

	int head = 1,tail = 0;

	for(register int i = 0;i <= 9;++i)

	{

		if(t[root].tr[i] != 0)

		{

			t[t[root].tr[i]].fail = root;

			q[++tail] = t[root].tr[i];

		}

	}

	while(head <= tail)

	{

		register int k = q[head++];

		for(int i = 0;i <= 9;++i)

		{

			if(t[k].tr[i] != 0)

			{

				int p = t[k].fail;

				while(p && t[p].tr[i] == 0)p = t[p].fail;

				t[t[k].tr[i]].fail = t[p].tr[i];

				t[t[k].tr[i]].tag |= t[t[p].tr[i]].tag;

				q[++tail] = t[k].tr[i];

			}

			else

			{

				t[k].tr[i] = t[t[k].fail].tr[i];

			}

		}

	}

	return;

}

typedef long long ll;

map<ll,ll> p;

inline ll encode(int len,int a,int b,int c,int d)

{

	ll res = len;

	res = res * (ptr + 1) + a;

	res = res * (ptr + 1) + b;

	res = res * (ptr + 1) + c;

	res = res * (ptr + 1) + d;//cout << len << " " << a << " " << b << " " << c << " " << d << "  " << res << endl;

	return res;

}

ll dfs(int len,int a,int b,int c,int d)

{

	if(t[a].tag || t[b].tag || t[c].tag || t[d].tag)return 0;

	if(len == 8)a = b = root;

	if(len == 7)c = d = root;

	if(len == 5)a = root;

	if(len == 4)b = d = root;

	if(len == 3)c = root;

	if(t[a].tag || t[b].tag || t[c].tag || t[d].tag)return 0;

	if(len == 0)return 1;

	register ll code = encode(len,a,b,c,d);

	if(p.find(code) != p.end())return p[code];

	register ll res = 0;

	for(int i = 0;i <= 9;++i)

	{

		res += dfs(len - 1,t[a].tr[i],t[b].tr[i],t[c].tr[i],t[d].tr[i]);

	}

	p[code] = res;

	return res;

}

int main()

{

	scanf("%d",&n);

	char str[8];

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

	{

		scanf("%s",str + 1);

		insert(str);

	}

	make_fail();

	register int cur = 0;cur = t[root].tr[1];

	printf("%lld\n",dfs(10,cur,cur,cur,cur));

	return 0;

}